Try   HackMD

2096. Step-By-Step Directions From a Binary Tree Node to Another


My Solution

The Key Idea for Solving This Coding Question

C++ Code

/** * 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; } };

Time Complexity

Space Complexity

Miscellane