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.
1class TreeNode:
2 def __init__(self, val):
3 self.val = val
4 self.left = None
5 self.right = None
6
7 def get_directions(self, startValue, destValue):
8 def path_to_node(root, value, path):
9 if not root:
10 return False
11 if root.val == value:
12 return True
13 path.append('L')
14 if path_to_node(root.left, value, path):
15 return True
16 path.pop()
17 path.append('R')
18 if path_to_node(root.right, value, path):
19 return True
20 path.pop()
21 return False
22
23 start_path, dest_path = [], []
24 path_to_node(self, startValue, start_path)
25 path_to_node(self, destValue, dest_path)
26
27 i = 0
28 while i < len(start_path) and i < len(dest_path) and start_path[i] == dest_path[i]:
29 i += 1
30 return 'U' * (len(start_path) - i) + ''.join(dest_path[i:])
31
32# Example usage:
33root = TreeNode(5)
34root.left = TreeNode(1)
35root.right = TreeNode(2)
36root.left.left = TreeNode(3)
37root.right.left = TreeNode(6)
38root.right.right = TreeNode(4)
39
40print(root.get_directions(3, 6)) # Output: "UURL"The code defines a TreeNode class with a method get_directions that computes the shortest path between two nodes in the form of directions. It uses a helper function path_to_node to traverse from the root to the specific node, appending 'L' or 'R' to a path list and returning True when the node is found. The main function finds paths to both start and destination nodes and calculates the direction by comparing the path steps. The paths are adjusted to determine when to move up and the remaining path to take.
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.
1using System;
2using System.Collections.Generic;
3
4public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
private Dictionary<int, TreeNode> parentMap = new Dictionary<int, TreeNode>();
private void DFS(TreeNode node, TreeNode parent) {
if (node == null) return;
parentMap[node.val] = parent;
DFS(node.left, node);
DFS(node.right, node);
}
private List<char> GetPath(int value) {
List<char> path = new List<char>();
while (parentMap.ContainsKey(value) && parentMap[value] != null) {
TreeNode parent = parentMap[value];
if (parent.left != null && parent.left.val == value) {
path.Add('L');
} else if (parent.right != null && parent.right.val == value) {
path.Add('R');
}
value = parent.val;
}
path.Reverse();
return path;
}
public string GetDirections(TreeNode root, int startValue, int destValue) {
DFS(root, null);
List<char> startPath = GetPath(startValue);
List<char> destPath = GetPath(destValue);
int i = 0;
while (i < startPath.Count && i < destPath.Count && startPath[i] == destPath[i]) {
i++;
}
return new string('U', startPath.Count - i) + string.Concat(destPath.GetRange(i, destPath.Count - i));
}
public static void Main(string[] args) {
TreeNode root = new TreeNode(5);
root.left = new TreeNode(1);
root.right = new TreeNode(2);
root.left.left = new TreeNode(3);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(4);
Solution sol = new Solution();
Console.WriteLine(sol.GetDirections(root, 3, 6)); // Output: "UURL"
}
}This C# implementation employs DFS to build a dictionary representing parent relationships, similar to the Python solution. It calculates paths from start and destination nodes up to their most recent common ancestor and uses these details to derive instructions for the needed path using 'L', 'R', and 'U'.