40 ms solution of C++ with 13 lines


  • 0
    S
    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            TreeNode* left = NULL;
            TreeNode* right = NULL;
            TreeNode* small = NULL;
            TreeNode* big = NULL;
            (p->val > q->val) ? (big = p, small = q) : (big = q, small = p); 
            if (root == p || root == q || root == NULL) return root;
            if (root->val > big->val) left = lowestCommonAncestor(root->left, small, big);
            else if (root->val < small->val) right = lowestCommonAncestor(root->right, small, big);
            else {
                left = lowestCommonAncestor(root->left, small, big);
                right = lowestCommonAncestor(root->right, small, big);
            }
            return left && right ? root : left ? left : right;
        }
    };

  • 0
    E

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
    if (!root || !p || !q)
    return NULL;

    	if (p == q)
    		return p;
    	else if (root == p || root == q)
    		return root;
    	else
    	{
    		TreeNode *small = p->val < q->val ? p : q;
    		TreeNode *big = p->val > q->val ? p : q;
    
    		if (big->val < root->val)
    		{
    			///go to left branch
    			return lowestCommonAncestor(root->left, p, q);
    		}
    		else if (small->val > root->val)
    		{
    			///go to right branch
    			return lowestCommonAncestor(root->right, p, q);
    		}
    		else
    			return root;
    	}
    

    }


Log in to reply
 

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