3 solutions with explanation


  • 5
    B

    The first one is straightforward but slow. The second one is also not difficult to come up with. The 3rd is neat and but it was hard for me to get my head around it at the first time.

       /**
         * Definition for a binary tree node.
         * struct TreeNode {
         *     int val;
         *     TreeNode *left;
         *     TreeNode *right;
         *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
         * };
         */
        class Solution {
        public:
            TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
                  return sol1(root,p,q);
                //return sol2(root,p,q);
                //return sol3(root,p,q);
            }
            
            // 23ms
            TreeNode* sol3(TreeNode* root, TreeNode* p, TreeNode* q) {
                 // no p and q
                 if (!root) return NULL;
                 // find either p or q
                 if (root == p || root == q) return root;
                 TreeNode *left = sol3(root->left,p, q);
                 TreeNode *right = sol3(root->right,p,q);
                 
                 // p and q are in different subtrees
                 if(left && right) return root;
                 // p and q are in the same subtree
                 return left ? left : right;
            }
            
            // 23ms   the lowest cross of the paths 
            TreeNode* sol2(TreeNode* root, TreeNode* p, TreeNode* q) {
                vector<TreeNode*> p1, p2;
                pathTo(root,p,p1);
                // if q in the path
                for (auto a : p1) {
                    if (q == a) return q;
                }
                pathTo(root,q,p2);
                for (auto a : p2) {
                    if (p == a) return p;
                }
                // if p in the path
                int N = p1.size();
                int M = p2.size();
                
                for (int i = N -1; i >= 0 ; i--) {
                    for (int j = M -1; j >=0 ;j--) {
                        if (p1[i] == p2[j]) {
                            return p1[i];
                        }
                    }
                }
                
                // should never come here
                return NULL;
            }
            
            bool pathTo(TreeNode* root, TreeNode* n, vector<TreeNode*> &path) {
                if (!root) return false;
                if (root == n) {
                    path.push_back(n);
                    return true;
                }
                
                path.push_back(root);
                if (pathTo(root->left, n, path)) return true;
                if (pathTo(root->right,n, path)) return true;
                path.pop_back();
                return false;
            }
        
            //slow....
            TreeNode* sol1(TreeNode* root, TreeNode* p, TreeNode* q) {
                if (p == root || q == root) return root;
                // 1 in left, 2 in right
                int lp = dfsFind(root->left,p) ? 1 : 2;
                int lq = dfsFind(root->left,q) ? 1 : 2;
                
                if (lp != lq) return root;
                if (lp == 1) return lowestCommonAncestor(root->left,p,q);
                return lowestCommonAncestor(root->right, p, q);
            }
            
            bool dfsFind(TreeNode *root, TreeNode *t) {
                if (!root) return false;
                if (root == t) return true;
                if (dfsFind(root->left,t)) return true;
                return dfsFind(root->right,t);
            }
        };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.