代码随想录27期|Python|Day18|二叉树|路径总和i&ii|找树左下角的值|从中序与后序遍历序列构造二叉树

?第一次刷的时候题解都不是精简版

?513. 找树左下角的值 - 力扣（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 findBottomLeftValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        res = 0
        queue = collections.deque()
        queue.append(root)
        while queue:
            size = len(queue)
            for i in range(size):
                cur = queue.popleft()
                # 当索引是队列的第一个值（也就是下一层最先被加入的节点）
                if i == 0:
                    res = cur.val
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
        return res

深度递归 + 回溯

?递归（左中右）也是最先寻找到左节点，所以只需要在求解最大深度的基础上，把遍历到最大深度的第一个值取出即可。

本题回溯思路可以参考之前的求解最大深度的方法。

# 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 findBottomLeftValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # 深度递归 + 回溯
        # 用self.定义全局变量
        self.max_depth = float('-inf')
        self.res = 0
        self.traversal(root, 0)
        return self.res
    
    def traversal(self, node, depth):  # depth 接受的是当前层的深度
        # 如果当前节点是叶子节点，判断当前深度是否是最大
        if not node.left and not node.right:
            # 更新最大深度
            if depth > self.max_depth:
                self.max_depth = depth
                self.res = node.val
            
        if node.left:
            depth += 1  # 深度 + 1
            self.traversal(node.left, depth)  # 此处传入的深度是子节点的深度
            depth -= 1  # 深度回溯 - 1
        if node.right:
            depth += 1
            self.traversal(node.right, depth)
            depth -= 1

?112. 路径总和 - 力扣（LeetCode）

重点是递归的返回值，传入参数，以及回溯部分的修改。

首先确定返回值，由于这一题不是遍历整个二叉树，而是找到满足条件的值就直接返回，所以返回值是bool。传入参数是需要一直更新和回溯的，这里是目标值和节点。

在递归中，我们自顶向下用目标值分别减去路径上的节点值，所以在递归结束之后，需要把这个值加回来。

还需要注意：在回溯到子节点返回True的时候，意味着这条路径是可行的，但是这个True只能返回到上一级的递归函数体里面。要返回到根节点的话需要一直向上返回到root，所以在左右子节点处理的时候我们在接受到底层传进来的True的时候需要再往上返回True。

# 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 hasPathSum(self, root, targetSum):
        """
        :type root: TreeNode
        :type targetSum: int
        :rtype: bool
        """
        if not root:
            return False
        return self.traversal(root, targetSum - root.val)

    # Step 1：传入参数（当前节点，目标值扣除当前节点值的结果）
    def traversal(self, node, count):
    # Step 2：终止条件
        # 1、count减到0，这条路径可行，返回给上一级
        if not node.left and not node.right and count == 0:
            return True 
        # 2、count没减到0，这条路径标记为false，返回给上一级
        if not node.left and not node.right:
            return False
    # Step 3：中间处理
        # 左节点 
        if node.left:
            count -= node.left.val  # 先扣除左子节点的值
            # 如果子节点遍历结果是True，那么这条路径有效，继续返回给上一级
            if self.traversal(node.left, count): return True
            count += node.left.val  # 回溯返还扣除的值
        # 右节点
        if node.right:
            count -= node.right.val
            if self.traversal(node.right, count): return True
            count += node.right.val
        
        return False

?113. 路径总和 II - 力扣（LeetCode）

本题在上一题的基础上要求返回全部满足条件的路径。

递归法

需要注意返回值：在本题中，由于设置的是全局变量，所以在递归函数中只需要对于变量进行更新，不需要有返回值，所以是return 即可。

另外本题可以学习如何使用Python类中的全局变量。

# 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 __init__(self):
        # 自定义全局变量保存结果和当前遍历的路径点
        self.res = []
        self.path = []

    # Step 1：确定返回值和参数
    # 由于是对于全局变量进行修改所以不需要返回值
    def traversal(self, node, count):
    
    # Step 2：确定终止条件
        # 当前节点是叶子节点，且count被减到0
        if not node.left and not node.right and count == 0:
            self.res.append(self.path[:])  # 满足条件的path全部保存
            return 
        # 当前节点是叶子节点，但是不满足条件，不修改全局变量直接返回
        if not node.left and not node.right:
            return 
    
    # Step 3：每次递归处理
        # 左节点
        if node.left:
            # 先加入路径点
            self.path.append(node.left.val)
            # count值减去左节点
            count -= node.left.val
            # 进入新的递归
            self.traversal(node.left, count)
            # count回溯
            count += node.left.val
            # 路径点回溯
            self.path.pop()
        # 右节点（同理）
        if node.right:
            self.path.append(node.right.val)
            count -= node.right.val
            self.traversal(node.right, count)
            count += node.right.val
            self.path.pop()
        return 

    def pathSum(self, root, targetSum):
        """
        :type root: TreeNode
        :type targetSum: int
        :rtype: List[List[int]]
        """
        if not root:
            return []
        # root不是空节点，先放入path中
        self.path.append(root.val)
        # 从根节点开始递归，传入参数是已经减掉root值的
        self.traversal(root, targetSum - root.val)

        return self.res

?迭代法

迭代在于对于栈的构建。本题采用的是由节点和通向该节点的路径组成的元组，其中路径的类型为由节点值组成的list。

# 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 pathSum(self, root, targetSum):
        """
        :type root: TreeNode
        :type targetSum: int
        :rtype: List[List[int]]
        """
        # 迭代
        if not root:
            return []
        res = []
        # 注意这个栈的内容：节点和到此节点路径
        stack = [(root, [root.val])]
        
        while stack:
            # Step 1：取出栈中元素
            node, path = stack.pop()
            # 判断当前节点是否是满足条件
            if not node.left and not node.right and sum(path) == targetSum:
                res.append(path) # 满足，加入res
            # Step 2：更新栈中的元素
            # 左节点
            if node.left:
                # 注意这里也需要按照（节点，路径）的元素加入栈
                stack.append((node.left, path + [node.left.val]))
                # path 是由值组成的数组，但是可能会出现空值的情况，所以用concatenate不是append
            # 右节点
            if node.right:
                stack.append((node.right, path + [node.right.val]))
        return res

?106. 从中序与后序遍历序列构造二叉树 - 力扣（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 buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        # 用后序子树来判断是因为和后续取root逻辑一致
        if not postorder:
            return None
        
        # 取出root节点的值（后序的最后一位）
        root_val = postorder[-1]
        root = TreeNode(root_val)  # 创建根节点
        
        # Step 1：在中序数组里找到root的值，作为切割点
        root_index = inorder.index(root_val)
        # 全部采用左闭右开区间（循环不变量）
        # [0, root_index) root_index已经被切走了
        left_inorder = inorder[:root_index]
        # [root_index + 1, end]
        right_inorder = inorder[root_index + 1 :]
        
        # Step 2：切割后序数组
        # 这里使用的是长度
        # [0, len(左子树))
        left_postorder = postorder[:len(left_inorder)]
        # (len(左子树), -1]  ：-1是因为root是post的最后一位，已经被取走了
        right_postorder = postorder[len(left_inorder): -1]

        # Step 3：递归
        root.left = self.buildTree(left_inorder, left_postorder)
        root.right = self.buildTree(right_inorder, right_postorder)

        return root

特别需要注意的是循环不变量（区间的开闭）。本题使用的是左闭右开。

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）?

?和上面的一样，但是在前序切片的时候是从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 buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if not preorder:
            return None

        root_val = preorder[0]
        root = TreeNode(root_val)

        root_index = inorder.index(root_val)

        left_inorder = inorder[:root_index]
        right_inorder = inorder[root_index + 1 : ]

        left_preorder = preorder[1 : len(left_inorder) + 1]
        right_preorder = preorder[len(left_inorder) + 1 : ]

        root.left = self.buildTree(left_preorder, left_inorder)
        root.right = self.buildTree(right_preorder, right_inorder)

        return root

第18天完结🎉