Tree
Depth-First Search
String
Backtracking
Binary Tree
Description
Given the root
of a binary tree, return all root-to-leaf paths in any order .
A leaf is a node with no children.
Example 1:
Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]
Example 2:
Input: root = [1]
Output: ["1"]
Constraints:
The number of nodes in the tree is in the range [1, 100]
.
-100 <= Node.val <= 100
Solutions
Solution 1
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 # 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 : Optional [ TreeNode ]):
if root is None :
return
t . append ( str ( root . val ))
if root . left is None and root . right is None :
ans . append ( "->" . join ( t ))
else :
dfs ( root . left )
dfs ( root . right )
t . pop ()
ans = []
t = []
dfs ( root )
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
37
38 /**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private List < String > ans = new ArrayList <> ();
private List < String > t = new ArrayList <> ();
public List < String > binaryTreePaths ( TreeNode root ) {
dfs ( root );
return ans ;
}
private void dfs ( TreeNode root ) {
if ( root == null ) {
return ;
}
t . add ( root . val + "" );
if ( root . left == null && root . right == null ) {
ans . add ( String . join ( "->" , t ));
} else {
dfs ( root . left );
dfs ( root . right );
}
t . remove ( t . size () - 1 );
}
}
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.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public :
vector < string > binaryTreePaths ( TreeNode * root ) {
vector < string > ans ;
vector < string > t ;
function < void ( TreeNode * ) > dfs = [ & ]( TreeNode * root ) {
if ( ! root ) {
return ;
}
t . push_back ( to_string ( root -> val ));
if ( ! root -> left && ! root -> right ) {
ans . push_back ( join ( t ));
} else {
dfs ( root -> left );
dfs ( root -> right );
}
t . pop_back ();
};
dfs ( root );
return ans ;
}
string join ( vector < string >& t , string sep = "->" ) {
string ans ;
for ( int i = 0 ; i < t . size (); ++ i ) {
if ( i > 0 ) {
ans += sep ;
}
ans += t [ i ];
}
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 /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func binaryTreePaths ( root * TreeNode ) ( ans [] string ) {
t := [] string {}
var dfs func ( * TreeNode )
dfs = func ( root * TreeNode ) {
if root == nil {
return
}
t = append ( t , strconv . Itoa ( root . Val ))
if root . Left == nil && root . Right == nil {
ans = append ( ans , strings . Join ( t , "->" ))
} else {
dfs ( root . Left )
dfs ( root . Right )
}
t = t [: len ( t ) - 1 ]
}
dfs ( root )
return
}
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 /**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function binaryTreePaths ( root : TreeNode | null ) : string [] {
const ans : string [] = [];
const t : number [] = [];
const dfs = ( root : TreeNode | null ) => {
if ( ! root ) {
return ;
}
t . push ( root . val );
if ( ! root . left && ! root . right ) {
ans . push ( t . join ( '->' ));
} else {
dfs ( root . left );
dfs ( root . right );
}
t . pop ();
};
dfs ( root );
return ans ;
}
GitHub