代码随想录算法训练营第16天｜513，112（重做），113（重

513. 找树左下角的值
     class Solution:
     def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
     if root is None:
     return 0
     queue = deque()
     queue.append(root)
     result = 0
     while queue:
     size = len(queue)
     for i in range(size):
     node = queue.popleft()
     if i == 0:
     result = node.val
     if node.left:
     queue.append(node.left)
     if node.right:
     queue.append(node.right)
     return result

514. 路经总和
     class Solution:
     def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
     if not root:
     return False
     if not root.left and not root.right and targetSum == root.val:
     return True

     return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)

106.构建二叉树
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
# 第一步: 特殊情况讨论: 树为空. 或者说是递归终止条件
if not preorder:
return None

    # 第二步: 前序遍历的第一个就是当前的中间节点.
    root_val = preorder[0]
    root = TreeNode(root_val)

    # 第三步: 找切割点.
    separator_idx = inorder.index(root_val)

    # 第四步: 切割inorder数组. 得到inorder数组的左,右半边.
    inorder_left = inorder[:separator_idx]
    inorder_right = inorder[separator_idx + 1:]

    # 第五步: 切割preorder数组. 得到preorder数组的左,右半边.
    # ⭐️ 重点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