112. 路径总和

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

深度优先遍历

# 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)

广度优先遍历

# 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 ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

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

---

深度优先遍历

重点在弹出的动作，方便下次遍历

# 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记录节点的父节点

理解起来相对更容易一点

# 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节点开始往下得到的路径和为目标值的路径个数 则原问题等于三个子问题的和： 根节点往下路径和为目标值的个数 左子树的解 右子树的解

# 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记录从根节点到当前节点的路径(不含当前节点)上每个节点的路径和

# 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 ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

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

深度优先遍历

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

# 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

广度优先遍历

# 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 ，返回其 最大路径和 。

递归

# 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