代码随想录27期|Python|Day17|二叉树|110.平衡二叉树 |257. 二叉树的所有路径 |404.左叶子之和

110. 平衡二叉树 - 力扣（LeetCode）

在递归后序遍历的基础上加上一个中间节点判断左右子节点的高度的步骤即可。

具体实现

是如果左右子树已经高度差大于1，则中间节点标记为-1，在逐层向上返回之后可以在root节点被判定为false；如果小于等于1，则保留左右节点高度较大的值+1作为当前中间节点的高度。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return False if self.getHeight(root) == -1 else True

    def getHeight(self, node):
        if not node:
            return 0
        # 取左高度
        left_height = self.getHeight(node.left)
        if left_height == -1:  # 如果已经是被标记过为-1，返回-1
            return -1
        # 取右高度
        right_height = self.getHeight(node.right)
        if right_height == -1:
            return -1
        # 中间节点处理
        if abs(right_height - left_height) > 1:
            res = - 1  # 高度差大于1，返回-1
        else:
            res = max(right_height, left_height) + 1  # 其余情况返回最大值作为当前节点的高度
        
        return res

257. 二叉树的所有路径 - 力扣（LeetCode）

首先确定遍历顺序，由于输出的结果是（root--leaf）的格式，显然使用前序遍历可以保存从中间节点开始的遍历顺序。

然后确定递归方法。这里在一般的中序遍历基础上考虑回溯（也就是在添加一个新的节点或由该节点引发的路径之后，需要在路径探索完毕后从叶子节点依次弹出路径记录的节点）。（图：代码随想录）

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        path = []  # 路径用来保存走过的路径，也是主要回溯的对象
        res =[]  # 结果用来保存输出的内容，是字符串组成的数组
        if not root:
            return res
        self.traversal(root, path, res)
        return res

    def traversal(self, node, path, res):
        path.append(node.val)  # 先保存传入节点的值
        # Step 1：确定终止条件。（中）
        # 当前节点的左右子节点都是空的时候，说明当前节点是叶子节点。按照格式保存
        if not node.left and not node.right:
            Str_path = '->'.join(map(str, path))
            res.append(Str_path)
            return  # return到上一级的节点所在的函数体
        # Step 2：左节点处理
        if node.left:
            self.traversal(node.left, path, res)
            path.pop()  # 在上一个函数执行完之后回溯，也就是从path中弹出刚刚加入的新节点
        # Step 3：右节点处理
        if node.right:
            self.traversal(node.right, path, res)
            path.pop()

本题也可以使用迭代算法+栈解决。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        # 迭代
        # 创建：结果，字符串路径，节点栈
        res, str_path, stack = [], [str(root.val)], [root]

        while stack:
            # 每次stack弹出一个节点
            cur = stack.pop()
            path = str_path.pop()
            if not cur.left and not cur.right:
                res.append(path)
            if cur.left:
                stack.append(cur.left)
                str_path.append(path + '->' + str(cur.left.val))
            if cur.right:
                stack.append(cur.right)
                str_path.append(path + '->' + str(cur.right.val))
        return res

404. 左叶子之和 - 力扣（LeetCode）

判断当前节点是否是左叶子节点必须依赖其父节点和其左右子节点空来判断。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def sumOfLeftLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # 先判断是否是空节点
        if not root:
            return 0
        # 在判断是否左右节点都是空，这样是没有左节点的
        if not root.left and not root.right:
            return 0
        
        left_value = self.sumOfLeftLeaves(root.left)
        # 需要同时满足：1.是父节点的左子节点；2.左右孩子节点都是空
        if root.left and not root.left.left and not root.left.right:
            left_value = root.left.val
        
        right_value = self.sumOfLeftLeaves(root.right)

        return left_value + right_value

第17天结束OMGGGGGG🎉