汇芳书院

专注计算机视觉、机器学习、分布式计算等领域, 兼聊投资、写作、生活

0%

二叉树的路径问题(系列)

发表于 更新于 分类于 Valine：
本文字数： 6.3k 阅读时长 ≈ 6 分钟

112. 路径总和

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

深度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        
        if not root.left and not root.right:
            return root.val == targetSum
        
        return self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)

广度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        
        node_queue = collections.deque([root])
        num_queue = collections.deque([root.val])
        while node_queue:
            node = node_queue.popleft()
            num = num_queue.popleft()
            if not node.left and not node.right:
                if num == targetSum:
                    return True
            else:
                if node.left:
                    node_queue.append(node.left)
                    num_queue.append(num+node.left.val)
                if node.right:
                    node_queue.append(node.right)
                    num_queue.append(num+node.right.val)
        return False

113. 路径总和 II

给你二叉树的根节点 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
25
26
27
# 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 pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        def dfs(root, path, ans, targetSum):
            # print(targetSum)
            if not root:
                return 
            path.append(root.val)
            if not root.left and not root.right:
                if targetSum == root.val:
                    ans.append(list(path))
            else:
                if root.left:
                    dfs(root.left, path, ans, targetSum-root.val)
                if root.right:
                    dfs(root.right, path, ans, targetSum-root.val)
            # 有点回溯的思路了，需要将加入的根节点弹出
            path.pop()
        path = []
        ans = []
        dfs(root, path, ans, targetSum)
        return ans

广度优先遍历

在找到和相等的节点时，需要反查到根节点。为此，需要有一个dict记录节点的父节点

理解起来相对更容易一点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# 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 pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        parents = dict()
        ans = []

        def getPath(node):
            path = collections.deque()
            while node:
                path.appendleft(node.val)
                node = parents[node]
            ans.append(list(path))
        
        if not root:
            return ans

        parents[root] = None
        node_queue = collections.deque([root])
        num_queue = collections.deque([0])
        while node_queue:
            node = node_queue.popleft()
            num = num_queue.popleft()
            total = num + node.val
            if not node.left and not node.right:
                # print(node.val,total,targetSum)
                if total == targetSum:
                    getPath(node)
            else:
                if node.left:
                    parents[node.left] = node
                    node_queue.append(node.left)
                    num_queue.append(total)
                if node.right:
                    parents[node.right] = node
                    node_queue.append(node.right)
                    num_queue.append(total)
        
        return ans

437. 路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

深度优先遍历

定义rootSum为从root节点开始往下得到的路径和为目标值的路径个数
则原问题等于三个子问题的和：
根节点往下路径和为目标值的个数
左子树的解
右子树的解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 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 pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        def rootSum(root, targetSum):
            ans = 0
            if not root:
                return ans
            
            if root.val == targetSum:
                ans += 1
            
            ans += rootSum(root.left, targetSum-root.val)
            ans += rootSum(root.right, targetSum-root.val)
            return ans
        
        if not root:
            return 0
        return rootSum(root, targetSum) + self.pathSum(root.left, targetSum) + self.pathSum(root.right, targetSum)

前缀路径和

【经典方法】
用dict记录从根节点到当前节点的路径(不含当前节点)上每个节点的路径和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 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 pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        prefix_sum = collections.defaultdict(int)
        prefix_sum[0] = 1
        def dfs(root, cur):
            ans = 0
            if not root:
                return ans

            cur += root.val
            ans += prefix_sum[cur-targetSum]

            prefix_sum[cur] += 1
            if root.left:
                ans += dfs(root.left, cur)
            if root.right:
                ans += dfs(root.right, cur)
            # 我们利用深度搜索遍历树，当我们退出当前节点时，我们需要及时更新已经保存的前缀和。
            prefix_sum[cur] -= 1
            return ans
        return dfs(root, 0)

257. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

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

深度优先遍历

题目要返回的是字符串形式的路径，表示无语

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 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 binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        def dfs(root, ans, path):
            if not root:
                return 
            path.append(str(root.val))
            if not root.left and not root.right:
                ans.append("->".join(path))
            else:
                if root.left:
                    dfs(root.left, ans, path)
                if root.right:
                    dfs(root.right, ans, path)
            path.pop()
        
        ans = []
        path = []
        dfs(root, ans, path)
        return ans

广度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 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 binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        def getPath(node):
            path = collections.deque()
            while node:
                path.appendleft(str(node.val))
                node = parents[node]
            ans.append('->'.join(path))

        ans = []
        if not root:
            return ans
        
        parents = dict()
        parents[root] = None
        node_queue = collections.deque([root])
        
        while node_queue:
            node = node_queue.popleft()
            if not node.left and not node.right:
                getPath(node)
            else:
                if node.left:
                    parents[node.left] = node
                    node_queue.append(node.left)
                if node.right:
                    parents[node.right] = node
                    node_queue.append(node.right)
        return ans

124. 二叉树中的最大路径和

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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.ans = float("-inf")
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        # maxGain计算以该节点为起点的一条路径，使得该路径上的节点值之和最大的贡献值
        def maxGain(root):
            if not root:
                return 0
            
            left = max(maxGain(root.left), 0)
            right = max(maxGain(root.right), 0)
            self.ans = max(self.ans, left+right+root.val)
            return max(left, right) + root.val
        maxGain(root)
        return self.ans

坚持原创分享，您的支持将鼓励我继续创作

欢迎关注我的其它发布渠道

------------- 本文结束,感谢阅读 如有问题可留言交流 -------------