My C++ solution, easy understand


  • 1
    S
     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || root == p || root == q)	return root;
    	TreeNode *left = lowestCommonAncestor(root->left, p, q);
    	TreeNode *right = lowestCommonAncestor(root->right, p, q);
    	if(left && right) return root;
    	return left? left : right;
    }

  • 0
    I

    clever !! it could also be used to solve LCA in binary tree~~


  • 0
    I

    if the tree is BST, the time complexity is would be O(n) because this solution doesn't examine the value of nodes( > or < ) , and if the tree is not BST would also be O(n), am I right?
    if the values are compared, the time complexity in BST would be O(logn) ??


  • 0
    S

    @Isabella_s : Yes, you are right. This problem's ideal time complexity of BST will be O(lgn). My solution's time complexity is O(n), so it is more suitable for the general tree.


  • 0
    M
    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            stack<TreeNode*> s1;
            stack<TreeNode*> s2;
            TreeNode* ptr=root;
            while(ptr!=NULL)
            {
                if(p->val>ptr->val)
                {
                    s1.push(ptr);
                    ptr=ptr->right;
                }else if(p->val<ptr->val)
                {
                    s1.push(ptr);
                    ptr=ptr->left;
                }else{
                        s1.push(ptr);
                        break;
                };
            };
            ptr=root;
            while(ptr!=NULL)
            {
                if(q->val>ptr->val)
                {
                    s2.push(ptr);
                    ptr=ptr->right;
                }else if(q->val<ptr->val)
                {
                    s2.push(ptr);
                    ptr=ptr->left;
                }else{
                        s2.push(ptr);
                        break;
                };
            }; 
            while(s1.size()>s2.size())
            {
                s1.pop();
            };
            while(s1.size()<s2.size())
            {
                s2.pop();
            };
            while(s1.top()!=s2.top())
            {
                s1.pop();
                s2.pop();
            };
            return s1.top();
            
            
            
        }
    };

Log in to reply
 

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