513. 找树左下角的值

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

题目链接/文章讲解/视频讲解：https://programmercarl.com/0513.找树左下角的值.html

思考

层序遍历秒了

# 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:
        queue = deque()
        queue.append(root)
        res = []
        while queue:
            level = []
            for i in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(level)
        return res[-1][0]

112.路径总和、113.路径总和ii

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

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

题目链接/文章讲解/视频讲解：https://programmercarl.com/0112.路径总和.html

112.路径总和
隐藏的回溯方法，sum每次提前减掉后传到下一步的。

# 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 root is None:
            return False
        if root.left is None and root.right is None:
            if root.val == targetSum:
                return True
            else:
                return False            
        elif root.left and not root.right:
            return self.hasPathSum(root.left,targetSum-root.val)
        elif not root.left and root.right:
            return self.hasPathSum(root.right,targetSum-root.val)
        else:
            return self.hasPathSum(root.right,targetSum-root.val) or self.hasPathSum(root.left,targetSum-root.val) 

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 __init__(self):
        self.sum = 0
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        path = []
        res = []
        def backtracking(root,targetSum):
            if root is None:
                return
            path.append(root.val)
            if root.left is None and root.right is None:
                if self.sum + root.val == targetSum:
                    res.append(path[:])
                return 
            if root.left:
                self.sum+=root.val
                backtracking(root.left,targetSum)
                self.sum-=root.val
                path.pop()
            if root.right:
                self.sum+=root.val
                backtracking(root.right,targetSum)
                self.sum-=root.val
                path.pop()
        backtracking(root,targetSum)
        return res

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

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

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

题目链接/文章讲解/视频讲解：https://programmercarl.com/0106.从中序与后序遍历序列构造二叉树.html