代码随想录算法训练营第十六天| 二叉树4

513. 找树左下角的值

本题递归偏难，反而迭代简单属于模板题， 两种方法掌握一下

题目链接/文章讲解/视频讲解：代码随想录

状态：递归，需看讲解

 先左后右遍历子树，因此，在得到底层最左边的叶子后，结果不会因为找到右边的叶子而更新

# 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 findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        self.result=None
        self.max_depth=float('-inf')
        self.traversal(root,0)
        return self.result

    def traversal(self,node,depth):
        if not node:
            return 
        if not node.left and not node.right:
            if depth>self.max_depth:
                self.max_depth=depth
                self.result=node.val
        self.traversal(node.left,depth+1)
        self.traversal(node.right,depth+1)

112. 路径总和

本题 又一次涉及到回溯的过程，而且回溯的过程隐藏的还挺深，建议先看视频来理解

112. 路径总和，和 113. 路径总和ii 一起做了。 优先掌握递归法。

题目链接/文章讲解/视频讲解：代码随想录

状态：递归加回溯，需要看思路

# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        return self.traveral(root,targetSum-root.val)
                
    def traveral(self,node,count):
        if not node.left and not node.right and count==0:
            return True
        if not node.left and not node.right:
            return False
        if node.left:
            count-=node.left.val
            if self.traveral(node.left,count):
                return True
            count+=node.left.val
        if node.right:
            count-=node.right.val
            if self.traveral(node.right,count):
                return True
            count+=node.right.val
        return False

113. 路径总和II

题目链接：113. 路径总和 II - 力扣（LeetCode）

 self.result.append(self.cur[:])

[:] 是切片操作符，self.cur[:] 会创建一个新的列表，它是 self.cur 的拷贝（深拷贝）。 如果直接使用 self.result.append(self.cur)，那么 self.result 中存储的是 self.cur 的引用。当 self.cur 在后续递归或回溯中发生改变时，self.result 中的路径也会跟着改变，这不是我们想要的行为。 使用 [:] 可以确保将当前路径的快照（即一个独立的副本）添加到结果中，即使后续修改了 self.cur，也不会影响 self.result 中已经保存的路径。

# 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 pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        self.result=[]
        if not root:
            return self.result
        self.cur=[root.val]
        self.traveral(root,targetSum-root.val)
        return self.result

    def traveral(self,node,count):
        if not node.left and not node.right and count==0:
            self.result.append(self.cur[:])
            return
        if not node.left and not node.right:
            return 
        if node.left:
            self.cur.append(node.left.val)
            count-=node.left.val
            self.traveral(node.left,count)
            count+=node.left.val
            self.cur.pop()
        if node.right:
            self.cur.append(node.right.val)
            count-=node.right.val
            self.traveral(node.right,count)
            count+=node.right.val
            self.cur.pop()
        return 

106. 从中序与后序遍历序列构造二叉树

 本题算是比较难的二叉树题目了，大家先看视频来理解。

106.从中序与后序遍历序列构造二叉树，105.从前序与中序遍历序列构造二叉树 一起做，思路一样的

题目链接/文章讲解/视频讲解：代码随想录

状态：看讲解

 需对列表进行切分

# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder:
            return None
        root_val=preorder[0]
        root=TreeNode(root_val)
        seperator_idx=inorder.index(root_val)

        inorder_left=inorder[:seperator_idx]
        inorder_right=inorder[seperator_idx+1:]

        preorder_left=preorder[1:1+len(inorder_left)]
        preorder_right=preorder[1+len(inorder_left):]

        root.left=self.buildTree(preorder_left,inorder_left)
        root.right=self.buildTree(preorder_right,inorder_right)
        return root

105. 从前序与中序遍历序列构造二叉树

# 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 buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not postorder:
            return None

        root_val = postorder[-1]
        root = TreeNode(root_val)

        separator_idx = inorder.index(root_val)

        inorder_left = inorder[:separator_idx]
        inorder_right = inorder[separator_idx + 1:]

        postorder_left = postorder[:len(inorder_left)]
        postorder_right = postorder[len(inorder_left): len(postorder) - 1]

        root.left = self.buildTree(inorder_left, postorder_left)
        root.right = self.buildTree(inorder_right, postorder_right)

        return root