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.
1#include <iostream>
2#include <vector>
3using namespace std;
4
5struct TreeNode {
6 int val;
7 TreeNode *left;
8 TreeNode *right;
9 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10};
11
12bool pathToNode(TreeNode* root, int value, vector<char>& path) {
13 if (!root) return false;
14 if (root->val == value) return true;
15 path.push_back('L');
16 if (pathToNode(root->left, value, path)) return true;
17 path.pop_back();
18 path.push_back('R');
19 if (pathToNode(root->right, value, path)) return true;
20 path.pop_back();
21 return false;
22}
23
24string getDirections(TreeNode* root, int startValue, int destValue) {
25 vector<char> startPath, destPath;
26 pathToNode(root, startValue, startPath);
27 pathToNode(root, destValue, destPath);
28 int i = 0;
29 while (i < startPath.size() && i < destPath.size() && startPath[i] == destPath[i]) i++;
30 return string(startPath.size() - i, 'U') + string(destPath.begin() + i, destPath.end());
31}
32
33int main() {
34 TreeNode* root = new TreeNode(5);
35 root->left = new TreeNode(1);
36 root->right = new TreeNode(2);
37 root->left->left = new TreeNode(3);
38 root->right->left = new TreeNode(6);
39 root->right->right = new TreeNode(4);
40
41 cout << getDirections(root, 3, 6) << endl; // Output: "UURL"
42
43 return 0;
44}This C++ implementation follows a similar logic to the Python solution. The pathToNode helper function finds paths to the target nodes using depth-first search, marking directions with 'L' and 'R'. The getDirections function then calculates steps towards the lowest common ancestor and outputs the directions to the destination node.
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 solution creates a map of parent nodes using a depth-first search traversal. Once the parent map is available, the method accumulates paths from start and destination nodes to the root by tracking their parent relationships. Both paths are assessed for shared parent nodes to identify the LCA depth. The excess upward steps in the start path are marked with 'U', and further navigation from the LCA to the destination is indicated by the recorded 'L'/'R' movements.