Untitled
unknown
plain_text
a year ago
2.0 kB
9
Indexable
/** * 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) {} * }; */ class Solution { public: string ans; void rootToStart(TreeNode* root, int startValue,int cnt) { if(root == NULL)return; if(root->val == startValue) { for(int i=0;i<cnt;i++) { ans.push_back('U'); } return; } rootToStart( root->left, startValue, cnt+1); rootToStart( root->right, startValue, cnt+1); } bool rootToDest(TreeNode* root, int destValue) { if(root == NULL)return false; if(root->val == destValue) { return true; } ans.push_back('L'); if(rootToDest(root->left, destValue)) return true; ans.pop_back(); ans.push_back('R'); if(rootToDest(root->right, destValue)) return true; ans.pop_back(); return false; } TreeNode* findLCA(TreeNode* root, int startValue, int destValue) { if(root == NULL)return NULL; if(root->val == startValue || root->val == destValue) return root; TreeNode* leftLCA = findLCA(root->left, startValue, destValue); TreeNode* rightLCA = findLCA(root->right, startValue, destValue); if(leftLCA == NULL) return rightLCA; if(rightLCA == NULL) return leftLCA; return root; } string getDirections(TreeNode* root, int startValue, int destValue) { TreeNode* lca = findLCA(root, startValue, destValue); rootToStart(lca, startValue, 0); rootToDest(lca, destValue); return ans; } };
Editor is loading...
Leave a Comment