# Leetcode: binary tree (4)

2020-11-10 10:44:09

This group consists of two binary trees How to find the sum of paths , Finally, make a little extension .

## 129. Sum Root to Leaf Numbers

Title Description : secondary ## Solution 1 ：dfs

Each floor needs to be multiplied by 10, Recursive implementation , consider dfs;
Use one sum To save the sum of the current path , use ans To save the sum of all current paths
Every child node ,sum = The value of the child node +sum*10 As the current path , Until you reach the leaf node ,ans = ans+sum.

``` 1 class Solution:
2     def sumNumbers(self, root: TreeNode) -> int:
3         if not root:
4             return 0
5         def dfs(root, sum): #  Recursive function , Enter the root node and sum, Output none , Constantly updated ans
6             sum = root.val + sum * 10
7             if not root.left and not root.right:
8                 self.ans += sum
9             if root.left:
10                 helper(root.left, sum)
11             if root.right:
12                 helper(root.right, sum)
13         self.ans = 0 #  You can also define a global variable , It's just relative to the inner function dfs
14         dfs(root, 0)
15         return self.ans```

## 112. Path Sum

Title Description : Simple ## Solution 1 ： recursive

Traverse all nodes , Give Way sum = sum - The value of this node , Then let the child node of the node also call hasPahSum function , Until you reach the leaf node , final sum If 0, It means that such a path has been found ;

Binary tree recursion is very routine to follow , Generally speaking , When the node is done , The others will be handed back to us ;
And trees are left-right branches , So in the end, the recursive function is returned in general (left) (and/or) Recursive function (right) that will do .

``` 1 class Solution:
2     def hasPathSum(self, root: TreeNode, sum: int) -> bool:
3         if not root: #  Empty tree
4             return False
5         sum -= root.val #  Every step recursion
6         if root.left == None and root.right == None: #  Recursion end condition
7             return (sum == 0)
8         return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum) #  As long as there is a path for True that will do .
9         #  Time complexity ： Visit each node once O(N).
10         #  Spatial complexity ： The worst case scenario when the tree is unbalanced is O(N). At best （ Trees are balanced ） Next is O(logN).```

## 113. Path Sum II

Title Description : secondary ## Solution 1 ： recursive

This problem requires that the path must start from the root node and reach the leaf node , So the idea is simple , take dfs:

Each time you enter recursion, you must first reduce the current node value , namely sum -= root.val

Recursive termination condition , If it's a leaf node (not root.left and not root.right), And path residue and sum = 0 了 , Add the result to the result array ;

If there are left subtrees , Recursive left subtree , Right subtree is the same ;

Be careful , Array in python Variable type in , there path+[root.val] It is equivalent to creating a new object on the stack , If you use append Indicates that no new object has been created, that is, the original object has been put on the stack , So make mistakes .

``` 1 class Solution(object):
2     def pathSum(self, root, sum):
3         """
4         :type root: TreeNode
5         :type sum: int
6         :rtype: List[List[int]]
7         ""
8         if not root: return []
9         ans = []
10         path = []
11         def dfs(root, path, sum):
12             sum -= root.val
13             if sum == 0 and not root.left and not root.right: #  Just change the line of business ：
14                 ans.append(path + [root.val])
15             if root.left:
16                 dfs(root.left, path+ [root.val], sum)
17             if root.right:
18                 dfs(root.right, path + [root.val], sum)
19         dfs(root, path, sum) #  Think about the first value you pass in , You can get the termination condition
20         return ans```

## 437. Path Sum III

Title Description : secondary ## Solution 1 ： recursive

This problem requires a path that does not necessarily start from the root node and does not have to reach the leaf node , Just change your mind a little bit ：

First of all, every time you enter recursion, you must first reduce the current node value , namely sum -= root.val

Recursive termination condition , Because there is no need to reach the leaf node , All you need is path residue and sum = 0 了 , The number of programs is +1;

If there are left subtrees , Recursive left subtree , Right subtree is the same ;

The above recursive function is inner recursion , Its meaning is from any root node to find the path to meet the conditions , Of course, we also need an outer recursive function , Here is our main function pathSum, Its meaning is to find a path from a root node , After traversing all the root nodes as the starting point .

We need a global variable self.ans To record the results .

``` 1 class Solution(object):
2     def __init__(self):
3         self.ans = 0
4     def pathSum(self, root, sum):
5         #  recursive , Depth-first search
6         #  situation 3： It doesn't have to start at the root , It doesn't have to end with the leaves
7         #  First write down the number of such programs
8         #  Ideas ： Double recursion
9         #  The outer recursion should be 113 Take a certain point as the starting point to find the path
10         #  Inner recursion starts at each point .
11         #  On this basis, the concrete solution can be realized .
12         def dfs(root, sum): #  Outer recursion , Take a point as a starting point to find a path
13             # if not root: #  The end condition
14             #     return
15             sum -= root.val
16             if sum == 0:
17                 self.ans += 1
18             if root.left:
19                 dfs(root.left, sum)
20             if root.right:
21                 dfs(root.right, sum)
22         #  The main function ：
23         #  The main function should not be set to zero every time self.res
24         if not root:
25             return self.ans
26         dfs(root, sum)
27         self.pathSum(root.left, sum)
28         self.pathSum(root.right, sum)
29         return self.ans```

## Expand

It's also the sum of similar paths , If we fix the root node , Path is defined as starting from the root , You don't need to reach the leaf node , To find out the specific path in this way .

## Solution 1 ： recursive

This problem requires that the path must start from the root node, but not necessarily to the leaf node , The idea is still the same , Just change the termination condition of recursion ：

Only the path residue and sum = 0 了 , Just add the result to the result array ;

If there are left subtrees , Recursive left subtree , Right subtree is the same ;

The difference from the previous question is , There is no need for outer recursive functions for this problem ;

``` 1 class Solution(object):
2     def pathSum(self, root, sum):
3         """
4         :type root: TreeNode
5         :type sum: int
6         :rtype: List[List[int]]
7         ""
8         if not root: return []
9         ans = []
10         path = []
11         def dfs(root, path, sum):
12             sum -= root.val
13             if sum == 0: #  Just change the line of business ：
14                 ans.append(path + [root.val])
15             if root.left:
16                 dfs(root.left, path+ [root.val], sum)
17             if root.right:
18                 dfs(root.right, path + [root.val], sum)
19         dfs(root, path, sum) #  Think about the first value you pass in , You can get the termination condition
20         return ans```