/**
* 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) {}
* };
*/
#define START (true)
class Solution {
public:
string getDirections(TreeNode* root, int startValue, int destValue) {
TreeNode *lca = findLCA(root, startValue, destValue);
string path1, path2;
findPath(lca, path1, startValue, START);
findPath(lca, path2, destValue, !START);
return path1 + path2;
}
private:
TreeNode *findLCA(TreeNode* root, int startValue, int destValue) {
if (!root) {
return nullptr;
}
if (root->val == startValue || root->val == destValue) {
return root;
}
TreeNode *leftSubtree = findLCA(root->left, startValue, destValue);
TreeNode *rightSubtree = findLCA(root->right, startValue, destValue);
if (!leftSubtree) {
return rightSubtree;
}
if (!rightSubtree) {
return leftSubtree;
}
return root;
}
TreeNode *findPath(TreeNode* root, string &path, int value, bool flag) {
if (!root) {
return nullptr;
}
if (root->val == value) {
return root;
}
if (flag == START) {
path.push_back('U');
} else {
path.push_back('L');
}
TreeNode *leftSubtree = findPath(root->left, path, value, flag);
if (!leftSubtree) {
path.pop_back();
} else {
return leftSubtree;
}
if (flag == START) {
path.push_back('U');
} else {
path.push_back('R');
}
TreeNode *rightSubtree = findPath(root->right, path, value, flag);
if (!rightSubtree) {
path.pop_back();
} else {
return rightSubtree;
}
return nullptr;
}
};
My Solution Solution 1: DFS (recursion) The Key Idea for Solving This Coding Question C++ Code /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right;
Jun 6, 2025MyCircularQueueO(k)
Apr 20, 2025O(m)
Mar 4, 2025O(n)n is the length of nums.
Feb 19, 2025or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up