Sponsored
Sponsored
This approach involves finding the path from the start node to the root and the destination node to the root. Using these paths, the Lowest Common Ancestor (LCA) of the start and destination nodes is determined. This allows us to break down the path from start to destination as moving up towards the root to the LCA, then down towards the destination. Once these steps are identified, we can replace moves with correct directions ('L', 'R', 'U').
Time Complexity: O(n), where n is the number of nodes, as each node could be traversed in the worst-case.
Space Complexity: O(h), where h is the height of the tree due to recursion stack and storing paths.
1import java.util.*;
2
3class TreeNode {
4 int val;
5 TreeNode left;
6 TreeNode right;
7
8 TreeNode(int x) {
9 val = x;
10 left = null;
11 right = null;
12 }
13}
14
15public class Solution {
16 private boolean pathToNode(TreeNode root, int value, List<Character> path) {
17 if (root == null) return false;
18 if (root.val == value) return true;
19
20 path.add('L');
21 if (pathToNode(root.left, value, path)) return true;
22 path.remove(path.size() - 1);
23
24 path.add('R');
25 if (pathToNode(root.right, value, path)) return true;
26 path.remove(path.size() - 1);
27
28 return false;
29 }
30
31 public String getDirections(TreeNode root, int startValue, int destValue) {
32 List<Character> startPath = new ArrayList<>();
33 List<Character> destPath = new ArrayList<>();
34
35 pathToNode(root, startValue, startPath);
36 pathToNode(root, destValue, destPath);
37
38 int i = 0;
39 while (i < startPath.size() && i < destPath.size() && startPath.get(i) == destPath.get(i)) i++;
40 StringBuilder sb = new StringBuilder();
41
42 for (int j = i; j < startPath.size(); j++) {
43 sb.append('U');
44 }
45 for (int j = i; j < destPath.size(); j++) {
46 sb.append(destPath.get(j));
47 }
48
49 return sb.toString();
50 }
51
52 public static void main(String[] args) {
53 TreeNode root = new TreeNode(5);
54 root.left = new TreeNode(1);
55 root.right = new TreeNode(2);
56 root.left.left = new TreeNode(3);
57 root.right.left = new TreeNode(6);
58 root.right.right = new TreeNode(4);
59
60 Solution sol = new Solution();
61 System.out.println(sol.getDirections(root, 3, 6)); // Output: "UURL"
62 }
63}The Java solution mirrors the logic of the Python and C++ implementations. It uses a recursive helper method to determine paths to the specified nodes and then constructs the necessary direction steps. The solution accounts for shared path segments leading to the lowest common ancestor.
This approach uses a DFS to build a parent map of nodes first. With this map, we can easily track the movement from any node to any other node. We then extract paths from startValue and destValue up to a common ancestor. The directions are computed through knowledge of parent-child relationships and mapped accordingly using 'L', 'R', and 'U'.
Time Complexity: O(n), traversing all nodes for setup. Space Complexity: O(n) due to the parent mapping.
1class TreeNode {
2
This JavaScript solution employs DFS to map out parent-child relationships. It calculates paths from the start and destination nodes up to the root and cross-references these paths: adjustments are then made based on common segments, with the creation of 'U' markers for upward movements away from the LCA, followed by directional 'L'/'R' commands to navigate towards the destination node.