Tree Path

Algorithms
tree
Catalogue
  1. 1. Path
    1. 1.1. 112. Path Sum
    2. 1.2. 113. Path Sum II
    3. 1.3. 437. Path Sum III
    4. 1.4. 666. Path Sum IV
    5. 1.5. 124. Binary Tree Maximum Path Sum
    6. 1.6. Maximum Sum from leaf to leaf
  2. 2. Path Sum + Prefix sum
    1. 2.1. Maximun Sum from any node to any node
  1. Case1: looks like “人” path.
  • We usually return integer value to parent node
  1. Case2: must through the root node

Path

112. Path Sum

  • root to leaf
  • True or False
1
2
3
4
5
6
7
8
9
class Solution(object):
    def hasPathSum(self, root, sum):
        if not root:
            return False

        if not root.left and not root.right:
            return sum == root.val

        return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)

113. Path Sum II

  • root to leaf
  • all results
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def pathSum(self, root, sum):
        res = []
        self.dfs(root, sum, [], res)
        return res

    def dfs(self, root, sum, path, res):
        if not root:
            return

        if not root.left and not root.right:
            if sum == root.val:
                res.append(path+[root.val])
            return

        self.dfs(root.left, sum-root.val, path+[root.val], res)
        self.dfs(root.right,sum-root.val, path+[root.val], res)

437. Path Sum III

  • from any node to any node in the tree (can be the same node)
1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def pathSum(self, root, sum):
        if not root: return 0

        return (self.findPaths(root, sum)
                + self.pathSum(root.left, sum)
                + self.pathSum(root.right, sum))

    def findPaths(self, root, sum):
        if not root:
            return 0
        return (sum == root.val) + self.findPaths(root.left, sum - root.val) + self.findPaths(root.right, sum - root.val)

666. Path Sum IV

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def pathSum(self, nums):
        nodes = {}
        for num in nums:
            nodes[(num/100, num%100/10)] = num%10
        self.res = 0
        self.dfs(1, 1, 0, nodes)
        return self.res

    def dfs(self, d, p, curSum, nodes):
        if (d, p) not in nodes:
            return
        curSum += nodes[(d, p)]
        left, right = (d+1, p*2-1), (d+1, p*2)
        if left not in nodes and right not in nodes:
            self.res += curSum
            return
        self.dfs(left[0], left[1], curSum, nodes)
        self.dfs(right[0], right[1], curSum, nodes)

124. Binary Tree Maximum Path Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def maxPathSum(self, root):
        self.res = -float('inf')
        self.dfs(root)
        return self.res

    def dfs(self, root):
        if not root:
            return 0
        left = max(0, self.dfs(root.left))
        right = max(0, self.dfs(root.right))
        self.res = max(self.res, left+right+root.val)
        return max(left, right) + root.val

Maximum Sum from leaf to leaf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def maxLeafSum(self, root):
        self.res = -float('inf')
        self.dfs(root)
        return self.res

    def dfs(self, root):
        if not root:
            return 0
        left = self.dfs(root.left)
        right = self.dfs(root.right)

        cur = left + right + root.val
        if cur > self.res and (root.left and root.right):
            self.res = cur

        if not root.left:
            return right
        elif not root.right:
            return left
        else:
            return max(left, right) + root.val

Path Sum + Prefix sum

Maximun Sum from any node to any node

Share