前言

今天是算法训练营的第十五天，到这里已经半个月了，状态相较于初期下降很明显。不说之前能赶着凌晨就把第二天的内容搞定，现在但凡某一天比较忙耽搁了，后面可能就会连着耽搁好几天，没写的文档越囤越多…..

110.平衡二叉树

题目链接：110. 平衡二叉树

题目描述：

给定一个二叉树，判断它是否是 平衡二叉树

思路

要判断平衡二叉树实际上是需要判断所有节点的左右子树高度差是否小于一，这种求高度的事情使用后序遍历比较合适。

从递归角度出发，使用递归三步法来分析：

1.首先是确定递归函数的参数和返回值

对于这个情景来说，我们需要后序遍历求出高度同时返回，所以参数是需要求高度的节点，返回值是高度。

 def getHeight(self, root: TreeNode) -> int:

2.确定终止条件

遇到空节点为此处的终止条件，由于没有高度，直接返回0

 if not root:
	return 0

3.明确单层递归的逻辑

在单层递归中，我们的目标是求出当前节点的左右子树高度差值，所以要做的就是分别求出左右子树高度然后求差，如果小于等于一说明此处依旧平衡，否则返回-1代表已经不是二叉平衡树了。

 def getHeight(self, root: TreeNode) -> int:
        if not root:
            return 0
        if (leftHeight := self.getHeight(root.left)) == -1:
            return -1
        if (rightHeight := self.getHeight(root.right)) == -1:
            return -1
        if abs(leftHeight - rightHeight) > 1:
            return -1
        else:
            return 1 + max(leftHeight, rightHeight)

递归法完整实现代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if self.getHeight(root) != -1:
            return True
        else:
            return False


    def getHeight(self, root: TreeNode) -> int:
        if not root:
            return 0
        if (leftHeight := self.getHeight(root.left)) == -1:
            return -1
        if (rightHeight := self.getHeight(root.right)) == -1:
            return -1
        if abs(leftHeight - rightHeight) > 1:
            return -1
        else:
            return 1 + max(leftHeight, rightHeight)

257.二叉树的所有路径

题目链接：257. 二叉树的所有路径

题目描述：

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

思路

由于是要记录出所有到达叶子节点的路径，这边使用前序遍历会比较合适，因为需要从根节点出发到叶子节点结束，这边要用到回溯的思想。

依旧是递归三步法：

1.首先确定递归函数的参数和返回值

这边由于是要记录路径进行回溯，以及找到路线后存放到结果集当中，我们总共需要传入三个参数:

cur记录当前节点、path记录路径用来回溯、result是结果集，没有返回值。

 def traversal(self, cur, path, result):

2.确定递归终止条件

终止条件好说，只要走到叶子节点了就可以进行终止了，这边我们找到叶子节点后，顺带将内容添加到结果集中，由于题目要求’->’所以此处还需要进行处理一下。

 if not cur.left and not cur.right:
    sPath = '->'.join(map(str,path))
    result.append(sPath)
    return

3.单步递归逻辑

简单来说，单步递归先把当前节点存放到路径集中以备回溯，如果已经找到叶子节点了，就讲目前的路径集添加进结果集返回。

这道题里回溯的思想很重要，我们在找到叶子节点之后需要回溯到上一步看看还有没有其他路径能走到叶子节点，所以这边我们需要在处理左孩子和右孩子时配套附上回溯逻辑。

 def traversal(self, cur, path, result):
        path.append(cur.val)
        if not cur.left and not cur.right:
            sPath = '->'.join(map(str,path))
            result.append(sPath)
            return
        if cur.left:
            self.traversal(cur.left, path, result)
            path.pop()
        if cur.right:
            self.traversal(cur.right, path, result)
            path.pop()

递归法完整实现代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        result = []
        path = []
        if not root:
            return result
        self.traversal(root, path, result)
        return result
        
    def traversal(self, cur, path, result):
        path.append(cur.val)
        if not cur.left and not cur.right:
            sPath = '->'.join(map(str,path))
            result.append(sPath)
            return
        if cur.left:
            self.traversal(cur.left, path, result)
            path.pop()
        if cur.right:
            self.traversal(cur.right, path, result)
            path.pop()
 ​

404.左叶子之和

题目链接：404. 左叶子之和

题目描述：

给定二叉树的根节点 root ，返回所有左叶子之和。

思路

这道题相较于上一道我觉得更容易想到一些，我们需要做的事情就是收集所有左叶子节点的值求和，由于中序遍历是先查看左，所以此处用中序遍历比较合适。

那么还是递归三步法：

1.确定递归函数参数和返回值：

参数只要传入一个树节点就行，返回值是整数和

 def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:

2.确定递归终止条件

这道题里我们只要找到左叶子并将和给记录即可，判断是否是左叶子只要判断该节点是否还有左孩子或右孩子节点。

 if root.left and not root.left.left and not root.left.right:
	leftValue = root.left.val

3.单次循环逻辑

这里遵循前序遍历逻辑，总体来说比较好理解

    leftValue = self.sumOfLeftLeaves(root.left)
    if root.left and not root.left.left and not root.left.right:
        leftValue = root.left.val
    rightValue = self.sumOfLeftLeaves(root.right)

递归法完整实现代码

 # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        if not root.left and not root.right:
            return 0
        
        leftValue = self.sumOfLeftLeaves(root.left)
        if root.left and not root.left.left and not root.left.right:
            leftValue = root.left.val
        
        rightValue = self.sumOfLeftLeaves(root.right)

        sumVal = leftValue + rightValue
        return sumVal

272.完全二叉树的节点个数

题目链接：222. 完全二叉树的节点个数

题目描述：

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~ 2h 个节点。

思路

这道题没怎么动脑子，用层序遍历直接秒了，记录下每一层大小再加起来就结束了。

层序遍历实现写法

 # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        queue = collections.deque([root])
        ans = 0
        while queue:
            levelSize = len(queue)
            ans += levelSize
            for _ in range(levelSize):
                node = queue.popleft()
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
        return ans

总结

今天的题目总体来说能理解思路，能感觉到递归在二叉树这一章节算是横着走，这边也是让我狠狠训练了一下递归。