Tree
Depth-First Search
String
Binary Tree
Description
You are given the root
of a binary tree with n
nodes. Each node is uniquely assigned a value from 1
to n
. You are also given an integer startValue
representing the value of the start node s
, and a different integer destValue
representing the value of the destination node t
.
Find the shortest path starting from node s
and ending at node t
. Generate step-by-step directions of such path as a string consisting of only the uppercase letters 'L'
, 'R'
, and 'U'
. Each letter indicates a specific direction:
'L'
means to go from a node to its left child node.
'R'
means to go from a node to its right child node.
'U'
means to go from a node to its parent node.
Return the step-by-step directions of the shortest path from node s
to node t
.
Example 1:
Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
Output: "UURL"
Explanation: The shortest path is: 3 → 1 → 5 → 2 → 6.
Example 2:
Input: root = [2,1], startValue = 2, destValue = 1
Output: "L"
Explanation: The shortest path is: 2 → 1.
Constraints:
The number of nodes in the tree is n
.
2 <= n <= 105
1 <= Node.val <= n
All the values in the tree are unique .
1 <= startValue, destValue <= n
startValue != destValue
Solutions
Solution 1
Python3 Java C++
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 # 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 getDirections (
self , root : Optional [ TreeNode ], startValue : int , destValue : int
) -> str :
edges = defaultdict ( list )
ans = None
visited = set ()
def traverse ( root ):
if not root :
return
if root . left :
edges [ root . val ] . append ([ root . left . val , 'L' ])
edges [ root . left . val ] . append ([ root . val , 'U' ])
if root . right :
edges [ root . val ] . append ([ root . right . val , 'R' ])
edges [ root . right . val ] . append ([ root . val , 'U' ])
traverse ( root . left )
traverse ( root . right )
def dfs ( start , dest , t ):
nonlocal ans
if start in visited :
return
if start == dest :
if ans is None or len ( ans ) > len ( t ):
ans = '' . join ( t )
return
visited . add ( start )
for d , k in edges [ start ]:
t . append ( k )
dfs ( d , dest , t )
t . pop ()
traverse ( root )
dfs ( startValue , destValue , [])
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69 /**
* 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 Map < Integer , List < List < String >>> edges ;
private Set < Integer > visited ;
private String ans ;
public String getDirections ( TreeNode root , int startValue , int destValue ) {
edges = new HashMap <> ();
visited = new HashSet <> ();
ans = null ;
traverse ( root );
dfs ( startValue , destValue , new ArrayList <> ());
return ans ;
}
private void traverse ( TreeNode root ) {
if ( root == null ) {
return ;
}
if ( root . left != null ) {
edges . computeIfAbsent ( root . val , k -> new ArrayList <> ())
. add ( Arrays . asList ( String . valueOf ( root . left . val ), "L" ));
edges . computeIfAbsent ( root . left . val , k -> new ArrayList <> ())
. add ( Arrays . asList ( String . valueOf ( root . val ), "U" ));
}
if ( root . right != null ) {
edges . computeIfAbsent ( root . val , k -> new ArrayList <> ())
. add ( Arrays . asList ( String . valueOf ( root . right . val ), "R" ));
edges . computeIfAbsent ( root . right . val , k -> new ArrayList <> ())
. add ( Arrays . asList ( String . valueOf ( root . val ), "U" ));
}
traverse ( root . left );
traverse ( root . right );
}
private void dfs ( int start , int dest , List < String > t ) {
if ( visited . contains ( start )) {
return ;
}
if ( start == dest ) {
if ( ans == null || ans . length () > t . size ()) {
ans = String . join ( "" , t );
}
return ;
}
visited . add ( start );
if ( edges . containsKey ( start )) {
for ( List < String > item : edges . get ( start )) {
t . add ( item . get ( 1 ));
dfs ( Integer . parseInt ( item . get ( 0 )), dest , t );
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
45
46
47
48
49
50
51
52
53
54
55 /**
* 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 :
unordered_map < int , vector < pair < int , char >>> edges ;
unordered_set < int > visited ;
string ans ;
string getDirections ( TreeNode * root , int startValue , int destValue ) {
ans = "" ;
traverse ( root );
string t = "" ;
dfs ( startValue , destValue , t );
return ans ;
}
void traverse ( TreeNode * root ) {
if ( ! root ) return ;
if ( root -> left ) {
edges [ root -> val ]. push_back ({ root -> left -> val , 'L' });
edges [ root -> left -> val ]. push_back ({ root -> val , 'U' });
}
if ( root -> right ) {
edges [ root -> val ]. push_back ({ root -> right -> val , 'R' });
edges [ root -> right -> val ]. push_back ({ root -> val , 'U' });
}
traverse ( root -> left );
traverse ( root -> right );
}
void dfs ( int start , int dest , string & t ) {
if ( visited . count ( start )) return ;
if ( start == dest ) {
if ( ans == "" || ans . size () > t . size ()) ans = t ;
return ;
}
visited . insert ( start );
if ( edges . count ( start )) {
for ( auto & item : edges [ start ]) {
t += item . second ;
dfs ( item . first , dest , t );
t . pop_back ();
}
}
}
};
GitHub