2096. Step-By-Step Directions From a Binary Tree Node to Another
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{"\n"} Output: "UURL"{"\n"} Explanation: The shortest path is: 3 → 1 → 5 → 2 → 6.{"\n"}
Example 2:
Input: root = [2,1], startValue = 2, destValue = 1{"\n"} Output: "L"{"\n"} Explanation: The shortest path is: 2 → 1.{"\n"}
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
Solution
Let denote the path from to .
First consider the case where goes through the root. Let's split this into . We can perform a DFS (depth first search) to get . This path consists of 'L's and 'R's. We can do another DFS to get . Replacing the 'L's and 'R's of with 'U's gives us . Now we can concatenate and to get the answer.
In the general case, may not go through the root. Notice that this path goes up a non-negative number of times (s) before going down a non-negative number of times (s or s). The highest node in this path is known as the LCA (lowest common ancestor) of and .
Here, and . Let's remove their longest common prefix, which is . We have and .
Then we replace all characters in with s to obtain . Finally, we get .
Time complexity
Each DFS takes and our string operations never happen on strings exceeding length . The time complexity is .
Space complexity
The strings never exceed length . The space complexity is .
C++ Solution
1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 * int val;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
10 * right(right) {}
11 * };
12 */
13class Solution {
14public:
15 void getPath(TreeNode *cur, int targetValue, string &path, string &ans) {
16 if (!cur)
17 return;
18 if (cur->val == targetValue)
19 ans = path;
20 path.push_back('L');
21 getPath(cur->left, targetValue, path, ans);
22 path.back() = 'R';
23 getPath(cur->right, targetValue, path, ans);
24 path.pop_back();
25 }
26
27 string getDirections(TreeNode *root, int startValue, int destValue) {
28 string tmpPath, startPath, destPath;
29 getPath(root, startValue, tmpPath, startPath);
30 getPath(root, destValue, tmpPath, destPath);
31 // Find the first point at which the paths diverge
32 auto [itr1, itr2] = mismatch(startPath.begin(), startPath.end(),
33 destPath.begin(), destPath.end());
34 return string(startPath.end() - itr1, 'U') +
35 string(itr2, destPath.end());
36 }
37};
Java Solution
1/**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 * int val;
5 * TreeNode left;
6 * TreeNode right;
7 * TreeNode() {}
8 * TreeNode(int val) { this.val = val; }
9 * TreeNode(int val, TreeNode left, TreeNode right) {
10 * this.val = val;
11 * this.left = left;
12 * this.right = right;
13 * }
14 * }
15 */
16class Solution {
17 // We use StringBuilder instead of String because String is immutable,
18 // so appending a character takes O(length of string).
19 // ans is a String[1] instead of String because in Java, arrays are passed by reference.
20 void getPath(TreeNode cur, int targetValue, StringBuilder path, String[] ans) {
21 if (cur == null)
22 return;
23 if (cur.val == targetValue)
24 ans[0] = path.toString();
25 int strLen = path.length();
26 path.append("L");
27 getPath(cur.left, targetValue, path, ans);
28 path.replace(strLen, strLen+1, "R");
29 getPath(cur.right, targetValue, path, ans);
30 path.delete(strLen, strLen+1);
31 }
32 public String getDirections(TreeNode root, int startValue, int destValue) {
33 StringBuilder tmpPath = new StringBuilder();
34 String[] startPath = {""}, destPath = {" "};
35 // Find the first point at which the paths diverge
36 getPath(root, startValue, tmpPath, startPath);
37 getPath(root, destValue, tmpPath, destPath);
38 int i = 0;
39 while (i < Math.min(startPath[0].length(), destPath[0].length()) && startPath[0].charAt(i) == destPath[0].charAt(i))
40 i++;
41 return "U".repeat(startPath[0].length()-i) + destPath[0].substring(i);
42 }
43}
Python Solution
1# Definition for a binary tree node. 2# class TreeNode: 3# def __init__(self, val=0, left=None, right=None): 4# self.val = val 5# self.left = left 6# self.right = right 7class Solution: 8 def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str: 9 # ans is a list so that it passes by reference 10 def getPath(cur, targetValue, path, ans): 11 if cur is None: 12 return 13 if cur.val == targetValue: 14 ans.append(''.join(path)); 15 path.append('L'); 16 getPath(cur.left, targetValue, path, ans) 17 path[-1] = 'R' 18 getPath(cur.right, targetValue, path, ans) 19 path.pop(-1) 20 21 tmpPath = [] 22 startPath = [] 23 destPath = [] 24 getPath(root, startValue, tmpPath, startPath) 25 getPath(root, destValue, tmpPath, destPath) 26 startPath = startPath[0] 27 destPath = destPath[0] 28 29 # Find the first point at which the paths diverge 30 i = 0 31 while i < min(len(startPath), len(destPath)) and startPath[i] == destPath[i]: 32 i += 1 33 return 'U'*(len(startPath)-i) + destPath[i:]
Which technique can we use to find the middle of a linked list?
Which of the following is the prefix sum of array [1, 2, 3, 4, 5]
?
Which data structure is used to implement recursion?
Which of the following problems can be solved with backtracking (select multiple)
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.