前言

今天是算法训练营的第十六天？实则并非，中间空了靠近8篇的总结没写，光做题不写总结效果差的离谱。终于，忙碌（不知道忙什么？）的生活重新回到正轨，回头补全先前缺下的笔记。

513.找树左下角的值

题目链接：513. 找树左下角的值

题目描述：

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

思路

想要找到最后一层最左边的的节点，那么看到这里肯定想到用层序遍历是最简单的了，我们只要返回最后一层的第一个元素即可，所以不具体讲了。

下面，我们来说说递归法如何实现。

递归法

说到递归法，想到的肯定是用前序遍历直接向左遍历到最后一个元素就返回，但这肯定不对。最左边的元素不一定是最后一层，所以，根据题目需求：首先是最后一层，然后再是最左边。

那么，使用递归法要怎么判断是不是最后一层呢？实际上记录下深度，深度最大的就是最后一层。想找最左边的元素就只要用前序遍历（哪个都无所谓，反正不要处理中）保证左边搜索优先，记录深度最大的叶子节点就好。

接下来是递归三部曲：

1.确定递归函数的参数和返回值

参数得有根节点，为了记录最长深度我们还需要一个深度参数。

不需要返回值

def traversal(self, root, depth):

2.确定终止条件

当遇到叶子节点的时候说明我们已经遍历到底了，这时候需要记录一下最大深度。

if root.left == None and root.right == None:
    if (depth > maxDepth):
        maxDepth = depth
        result = root.val
    return

3.确定单层递归逻辑

使用回溯来记录每个元素的深度

if root.left:
    depth += 1
    self.traversal(root.left, depth)
    depth -= 1
if root.right:
    depth += 1
    self.traversal(root.right, depth)
    depth -= 1

完成实现写法

层序遍历法

# 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:
        if not root:
            return 0
        queue = collections.deque([root])
        ans = 0
        while queue:
            levelSize = len(queue)
            ans = queue[0].val
            for _ in range(levelSize):
                node = queue.popleft()
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
        return ans

递归法

# 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, result = 0, depth = 0):
        self.maxDepth = depth
        self.result = result

    def traversal(self, root, depth):
        if root.left == None and root.right == None:
            if (depth > self.maxDepth):
                self.maxDepth = depth
                self.result = root.val
            return
        if root.left:
            depth += 1
            self.traversal(root.left, depth)
            depth -= 1
        if root.right:
            depth += 1
            self.traversal(root.right, depth)
            depth -= 1
        
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        self.maxDepth = float('-inf')
        self.result = 0
        self.traversal(root, 0)
        return self.result

112.路径总和

题目链接：112. 路径总和

题目描述：

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

思路

这道题需要使用到一些回溯的技巧，在初见时还没操作回溯的经验，当时觉得很难理解。

这边主要介绍递归法的思路：

判断路径总和，我们使用深度优先遍历，接下来是递归三部曲：

1.确定递归函数的参数和返回类型

参数主要是根节点和需要的目标数值，另外我加了一个sumnow参数来记录目前的总和

返回类型是布尔值，返回是否符合条件

def backtracing(self, root, targetSum, sumnow):

2.确定终止条件

如果遍历到叶子节点，并且sumnow与targetSum值相等，那么说明符合条件返回True，否则返回False。

if root.left == None and root.right == None and sumnow == targetSum:
    return True
if root.left == None and root.right == None:
    return False

3.确定单层循环逻辑

这边需要利用到回溯的思想，每次处理完后减去新加的值再去遍历新的路径

if root.left:
    sumnow += root.left.val
    if self.backtracing(root.left, targetSum, sumnow):
        return True
    sumnow -= root.left.val
if root.right:
    sumnow += root.right.val
    if self.backtracing(root.right, targetSum, sumnow):
        return True
    sumnow -= root.right.val

整体实现写法

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

拓展题：113.路径总和ii

题目链接：113. 路径总和 II

题目描述：

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

这道题和上一道没啥区别，唯一区别就是上一道判断是否有路径，这道题输出路径，下面直接给出写法：

# 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 backtracing(self, root, targetSum, sumnow, path, result):
        if root.left == None and root.right == None and sumnow == targetSum:
            result.append(path[:])
            return result
        if root.left:
            sumnow += root.left.val
            path.append(root.left.val)
            self.backtracing(root.left, targetSum, sumnow, path, result)
            path.pop()
            sumnow -= root.left.val
        if root.right:
            sumnow += root.right.val
            path.append(root.right.val)
            self.backtracing(root.right, targetSum, sumnow, path, result)
            path.pop()   
            sumnow -= root.right.val
        

    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        if not root:
            return []
        result = []
        self.backtracing(root, targetSum, root.val, [root.val], result)
        return result

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

题目链接：106. 从中序与后序遍历序列构造二叉树

题目描述：

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

思路

构造二叉树还是比较容易的，我们需要抓住一个要素：后序遍历最后一个元素是根节点、前序遍历第一个元素是根节点。

如果知道哪个元素是根节点，那么下一步就是对中序遍历进行分析，中序遍历中根节点左边的是左子树，右边的是右子树。

由此分割出左右子树后，我们又可以根据分割完的中序遍历与后续遍历进行子树的根节点查找并重复之前的操作，最终就能把整棵树构建出了。

实现写法

# 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 
        
        root_val = postorder[-1]
        root = TreeNode(root_val)

        cut_idx = inorder.index(root_val)

        inorder_left = inorder[:cut_idx]
        inorder_right = inorder[cut_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

总结

这一天的题目总体来说还是挺有意思的，隔了八天重新回顾发现也能很快就得到思路。

除此以外，初次做112时还没有学习回溯，当时理解得很模糊，在学习之后很快就能理解到精髓所在从而轻松AC，非常直观地感受到了学习的成效。