代码随想录算法训练营第十八天 | LeetCode513 找树左下角的值、LeetCode112 路径总和、LeetCode113 路径总和Ⅱ、LeetCode106 从中序与后序遍历序列构建二叉树、LeetCode105 从前序与中序遍历序列构造二叉树

今日任务：

LeetCode513 找树左下角的值
LeetCode112 路径总和、LeetCode113 路径总和Ⅱ
LeetCode106 从中序与后序遍历序列构建二叉树、LeetCode105 从前序与中序遍历序列构造二叉树

资料来源：

1 LeetCode513 找树左下角的值

题目

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

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

示例 1:


输入: root = [2,1,3]
输出: 1

示例 2:


输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

提示:

二叉树的节点个数的范围是 [1,104]
$-2^{31}$ <= Node.val <= $2^{31} - 1$

这题确实是迭代简单得多，第一次做的时候直接迭代出的结果。先在队列里迭代到最后一层，然后在向队列中添加元素的时候，故意将左侧元素放在右侧元素后面添加，这样最后遍历到的元素一定会因为是叶子元素而修改result，也一定是最左侧的元素。

另外，这题不能使用先放左侧元素后放右侧元素，遇到叶子节点直接返这样的方法，防的是这样的二叉树：

python
# 我的代码
from collections import deque
from typing import Optional

# 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)
        result = 0
        while len(queue) != 0:
            size = len(queue)
            for _ in range(size):
                node = queue.popleft()
                if node.left is None and node.right is None:
                    result = node.val
                if node.right is not None:
                    queue.append(node.right)
                if node.left is not None:
                    queue.append(node.left)
        return result

这题也可以递归写，只是有点麻烦，递归要找的就是“深度最大的左节点”了。要记得在递归的过程中把记录的深度进行回溯。

python
from typing import Optional

# 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.depth = 0
        self.result = 0
        self.max_depth = 0

    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        self.traversal(root)
        return self.result

    def traversal(self, root: TreeNode):
        self.depth += 1
        if root.right is None and root.left is None:
            if self.max_depth < self.depth:
                self.max_depth = self.depth
                self.result = root.val
        else:
            # 在这里保证了优先找左节点 所以一旦到达了更深的一层 在上面的代码中第一个被更新的一定是左节点
            if root.left is not None:
                self.traversal(root.left)
                self.depth -= 1  # 回溯
            if root.right is not None:
                self.traversal(root.right)
                self.depth -= 1  # 回溯

2 LeetCode112 路径总和、LeetCode113 路径总和Ⅱ

题目

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

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

（路径之和Ⅱ要求返回满足targetSum的所有路径）

示例 1：


输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：


输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：


输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

提示：

树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

一眼递归，记得回溯即可。这个题也有迭代写法，用栈模拟递归即可。

python
# 路径之和
from typing import Optional

# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if root is None:
            return False
        return self.traversal(root, targetSum)

    def traversal(self, root: TreeNode, targetSum: int) -> bool:
        self.sum += root.val  # 进入下一个节点
        if root.left is None and root.right is None:
            return self.sum == targetSum
        left = False
        if root.left is not None:
            left = self.traversal(root.left, targetSum)
            self.sum -= root.left.val # 回溯
        right = False
        if root.right is not None:
            right = self.traversal(root.right, targetSum)
            self.sum -= root.right.val # 回溯
        if left or right:
            return True
        else:
            return False

python
# 路径之和Ⅱ
from typing import Optional, List

# 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.result_ = []
        self.path = []

    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        if root is None:
            return []
        self.traversal(root, targetSum)
        return self.result_

    def traversal(self, root: TreeNode, targetSum: int):
        self.path.append(root.val)
        if root.right is None and root.left is None:
            if sum(self.path) == targetSum:
                self.result_.append(self.path.copy())  # copy必须 否则进去的只有地址
                return
        if root.left is not None:
            self.traversal(root.left, targetSum)
            self.path.pop()  # 回溯
        if root.right is not None:
            self.traversal(root.right, targetSum)
            self.path.pop()  # 回溯

3 LeetCode106 从中序与后序遍历序列构建二叉树、LeetCode105 从前序与中序遍历序列构造二叉树

题目

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

（第二个题给的就是前序和中序遍历序列）

示例 1:


输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:


输入：inorder = [-1], postorder = [-1]
输出：[-1]

提示:

1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由不同的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历

总的原理就是利用后序/前序的根节点在最后/最前的特性对中序和后序/前序序列进行切割，将左子树和右子树的序列切割出来。大体上就是这么一个步骤：

如果传入的序列长度为0，说明已经到头了，直接返回None
如果传入的序列长度为1，说明到的是叶子节点，按照这个序列里唯一的元素创建节点返回即可。
在其他情况下，要将传入的序列分割为左子树、根节点和右子树。利用后序/前序先找到根节点并且创建节点，再利用这个根节点的值在中序序列里寻找对应的元素位置。这个元素位置是可以将中序和后序/前序序列一起切开的（因为两个序列的左子树，右子树序列长度一定相等！）
将后序/前序序列和中序序列的左子树/右子树部分分别进行下一层的递归，并且让根节点的左右子节点指向下一层递归的返回值。

python
# 中序 后序
from typing import List, Optional

# 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]:
        return self.traversal(inorder, postorder)

    def traversal(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if len(postorder) == 0:
            return None
        if len(postorder) == 1:
            return TreeNode(val=postorder[0])
        else:
            node = TreeNode(val=postorder[-1])
            # 先切中序 这个index定到了后序的-1 切中序的同时就已经把后序切完了 因为两个遍历的左子树位置是一样的
            inorder_index = 0
            for inorder_index in range(len(inorder)):
                if inorder[inorder_index] == postorder[-1]:
                    break
            node.left = self.traversal(inorder[0:inorder_index], postorder[0:inorder_index])
            node.right = self.traversal(inorder[inorder_index+1:], postorder[inorder_index:-1])
            return node

python
# 前序 中序
from typing import List, Optional

# 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]:
        return self.traversal(preorder, inorder)

    def traversal(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if len(preorder) == 0:
            return None
        if len(preorder) == 1:
            return TreeNode(val=preorder[0])
        else:
            node = TreeNode(val=preorder[0])
            index = 0
            for index in range(len(inorder)):
                if inorder[index] == preorder[0]:
                    break
            node.left = self.traversal(preorder[1:index+1], inorder[0:index])
            node.right = self.traversal(preorder[index+1:], inorder[index+1:])
            return node

目录

1 LeetCode513 找树左下角的值

2 LeetCode112 路径总和、LeetCode113 路径总和Ⅱ

3 LeetCode106 从中序与后序遍历序列构建二叉树、LeetCode105 从前序与中序遍历序列构造二叉树