1
class Solution:
2
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
3
        self.max_depth = float('-inf')  # 初始化最大深度
4
        self.res = 0  # 存储最终结果
5
        self.traverse(root, 0)  # 从深度 0 开始遍历
6
        return self.res
7

8
    def traverse(self, root, depth):
9
        if not root.left and not root.right:
10
            # 如果当前节点是叶子节点且深度大于最大深度，则更新结果
11
            if depth > self.max_depth:
12
                self.max_depth = depth
13
                self.res = root.val
14
                return
15
        if root.left:
16
            depth += 1
17
            self.traverse(root.left, depth)
18
            depth -= 1
19
        if root.right:
20
            depth += 1
21
            self.traverse(root.right, depth)
22
            depth -= 1

1
class Solution:
2
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
3
        if not root:
4
            return False
5
        self.target = targetSum  # 设置目标和
6
        return self.traverse(root, root.val)
7

8
    def traverse(self, root, sum_val):
9
        # 如果当前节点是叶子节点且路径和等于目标值，则返回 True
10
        if not root.left and not root.right and self.target == sum_val:
11
            return True
12
        # 如果当前节点是叶子节点但路径和不等于目标值，则返回 False
13
        if not root.left and not root.right:
14
            return False
15
        if root.left:
16
            sum_val += root.left.val
17
            if self.traverse(root.left, sum_val):
18
                return True
19
            sum_val -= root.left.val  # 回溯
20
        if root.right:
21
            sum_val += root.right.val
22
            if self.traverse(root.right, sum_val):
23
                return True
24
            sum_val -= root.right.val  # 回溯
25
        return False

1
class Solution:
2
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
3
        self.res = []  # 存储所有符合条件的路径
4
        if not root:
5
            return self.res
6
        self.target = targetSum  # 设置目标和
7
        path = []
8
        path.append(root.val)  # 添加根节点值
9
        self.traverse(root, root.val, path)
10
        return self.res
11

12
    def traverse(self, root, sum_val, path):
13
        if not root.left and not root.right and self.target == sum_val:
14
            # 找到一条路径，深拷贝加入结果
15
            self.res.append(path[:])
16
            return
17
        if root.left:
18
            sum_val += root.left.val
19
            path.append(root.left.val)
20
            self.traverse(root.left, sum_val, path)
21
            sum_val -= root.left.val
22
            path.pop()  # 回溯
23
        if root.right:
24
            sum_val += root.right.val
25
            path.append(root.right.val)
26
            self.traverse(root.right, sum_val, path)
27
            sum_val -= root.right.val
28
            path.pop()  # 回溯

1
class Solution:
2
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
3
        # 用于记录中序遍历中每个值的索引，方便快速查找
4
        self.index = {}
5
        for i in range(len(inorder)):
6
            self.index[inorder[i]] = i
7
        return self.build(preorder, 0, len(preorder) - 1, inorder, 0, len(inorder) - 1)
8

9
    def build(self, preorder, p_start, p_end, inorder, i_start, i_end):
10
        # 当前序遍历的起始索引大于结束索引时，说明没有节点可以构造，返回 None
11
        if p_start > p_end:
12
            return None
13
        # 前序遍历的第一个元素是根节点
14
        root_val = preorder[p_start]
15
        # 在中序遍历中找到根节点的索引
16
        index = self.index[root_val]
17
        # 计算左子树的大小
18
        left_size = index - i_start
19
        root = TreeNode(root_val)
20
        # 递归构建左子树和右子树
21
        # 左子树的前序遍历范围是从 p_start + 1 到 p_start + left_size
22
        # 右子树的前序遍历范围是从 p_start + left_size + 1 到 p_end
23
        # 左子树的中序遍历范围是从 i_start 到 index - 1
24
        # 右子树的中序遍历范围是从 index + 1 到 i_end
25
        root.left = self.build(preorder, p_start + 1, p_start + left_size, inorder, i_start, index - 1)
26
        root.right = self.build(preorder, p_start + left_size + 1, p_end, inorder, index + 1, i_end)
27
        return root

1
class Solution:
2
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
3
        # 用于记录中序遍历中每个值的索引，方便快速查找
4
        self.index = {}
5
        for i in range(len(inorder)):
6
            self.index[inorder[i]] = i
7
        return self.build(inorder, 0, len(inorder) - 1, postorder, 0, len(postorder) - 1)
8

9
    def build(self, inorder, i_start, i_end, postorder, p_start, p_end):
10
        # 当前后序遍历的起始索引大于结束索引时，说明没有节点可以构造，返回 None
11
        if i_start > i_end or p_start > p_end:
12
            return None
13
        root_val = postorder[p_end]  # 后序遍历最后一个元素是根节点
14
        index = self.index[root_val]  # 在中序中找到根节点索引
15
        left_size = index - i_start  # 左子树节点数
16
        root = TreeNode(root_val)
17
        # 递归构建左子树和右子树
18
        # 左子树的后序遍历范围是从 p_start 到 p_start + left_size - 1
19
        # 右子树的后序遍历范围是从 p_start + left_size 到 p_end - 1
20
        # 左子树的中序遍历范围是从 i_start 到 index - 1
21
        # 右子树的中序遍历范围是从 index + 1 到 i_end
22
        root.left = self.build(inorder, i_start, index - 1, postorder, p_start, p_start + left_size - 1)
23
        root.right = self.build(inorder, index + 1, i_end, postorder, p_start + left_size, p_end - 1)
24
        return root