python coding with ChatGPT 打卡第17天| 二叉树：找树左下角的值、路径总和

相关推荐
python coding with ChatGPT 打卡第12天| 二叉树：理论基础
python coding with ChatGPT 打卡第13天| 二叉树的深度优先遍历
python coding with ChatGPT 打卡第14天| 二叉树的广度优先遍历
python coding with ChatGPT 打卡第15天| 二叉树：翻转二叉树、对称二叉树
python coding with ChatGPT 打卡第16天| 二叉树：完全二叉树、平衡二叉树、二叉树的所有路径、左叶子之和

找树左下角的值

Key Points

找出树的最后一行的最左边的值

相关题目

513. 找树左下角的值

视频讲解

递归中带着回溯

重点分析

方法一：层序遍历

def findBottomLeftValue(root):
    queue_record = [root]
    res = root.val
    while queue_record:
        level_size = len(queue_record)
        for i in range(level_size):
            node = queue_record.pop(0)
            if i==0:
                res = node.val
            if node.left:
                queue_record.append(node.left)
            if node.right:
                queue_record.append(node.right)
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

方法二：层序遍历简洁版

class Solution(object):
    def findBottomLeftValue(self, root):
        if not root:
            return None

        queue = [root]
        while queue:
            current = queue.pop(0)
            # 先右后左加入队列，确保左边的节点最后被处理，从而保留在current中
            if current.right:
                queue.append(current.right)
            if current.left:
                queue.append(current.left)

        # 循环结束时，current中存储的是最后一层最左边的节点
        return current.val
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这段代码使用了BFS来确保按层遍历树的节点，并且通过在每层遍历时记录遍历到的第一个节点值，最终找到了最后一行最左边的值。请注意，这里故意先将右子节点加入队列，然后加入左子节点，是为了在处理每一层的节点时，最后处理左子节点，但是对于寻找最后一行最左边的值的目的而言，只需要记录每一层第一次访问的节点即可，因此实际上你可以按照正常的顺序（先左后右）加入队列，然后最后处理的节点即为所求。这样的处理方式更直观且易于理解。

方法三：递归法

class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
        self.max_depth = float('-inf')
        self.result = None
        self.traversal(root, 0)
        return self.result
    
    def traversal(self, node, depth):
        if not node.left and not node.right:
            if depth > self.max_depth:
                self.max_depth = depth
                self.result = node.val
            return
        
        if node.left:
            self.traversal(node.left, depth+1)
        if node.right:
            self.traversal(node.right, depth+1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

递归的另一种写法，由ChatGPT提供

路径总和

Key Points

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

相关题目

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

视频讲解

路径总和

重点分析

112
方法一：递归

def hasPathSum(root: TreeNode, targetSum: int) -> bool:
    if not root:
        return False
    
    # 更新目标和
    targetSum -= root.val
    
    # 如果是叶子节点，检查目标和是否为0
    if not root.left and not root.right:
        return targetSum == 0
    
    # 递归遍历左右子节点
    return hasPathSum(root.left, targetSum) or hasPathSum(root.right, targetSum)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

方法二：迭代法

def hasPathSum(root, targetSum):
    if not root:
        return False

    stack_record = [(root, root.val)]

    while stack_record:
        node, value = stack_record.pop()
        if not node.left and not node.right:
            if value == targetSum:
                return True
        else:
            if node.right:
                stack_record.append((node.right, value+node.right.val))
            if node.left:
                stack_record.append((node.left, value + node.left.val))
    return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

113 方法一：递归法

class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> [[int]]:
        result = []
        self.dfs(root, targetSum, [], result)
        return result
    
    def dfs(self, node, targetSum, path, result):
        if not node:
            return
        # 添加当前节点到路径
        path.append(node.val)
        # 检查是否是叶子节点且路径总和等于目标和
        if not node.left and not node.right and sum(path) == targetSum:
            result.append(list(path))
        else:
            # 递归遍历左右子节点
            self.dfs(node.left, targetSum, path, result)
            self.dfs(node.right, targetSum, path, result)
        # 回溯前去除当前节点
        path.pop()

# 示例使用
# 假设有一个二叉树和目标和，可以创建TreeNode实例并调用Solution().pathSum(root, targetSum)来获取结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

方法二：迭代法

def pathSum(root, targetSum):
    if not root:
        return []

    stack_record = [(root, [root.val])]
    res = []

    while stack_record:
        node, value_list = stack_record.pop()
        if not node.left and not node.right:
            if sum(value_list) == targetSum:
                res.append(value_list)
        else:
            if node.right:
                stack_record.append((node.right, value_list+[node.right.val]))
            if node.left:
                stack_record.append((node.left, value_list + [node.left.val]))
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18