Easy C++ Recursive and Iterative Solutions


  • 76

    Well, remember to take advantage of the property of binary search trees, which is, node -> left -> val < node -> val < node -> right -> val. Moreover, both p and q will be the descendants of the root of the subtree that contains both of them. And the root with the largest depth is just the lowest common ancestor. This idea can be turned into the following simple recursive code.

    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            if (p -> val < root -> val && q -> val < root -> val)
                return lowestCommonAncestor(root -> left, p, q);
            if (p -> val > root -> val && q -> val > root -> val)
                return lowestCommonAncestor(root -> right, p, q);
            return root;
        }
    };
    

    Of course, we can also solve it iteratively.

    class Solution { 
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            TreeNode* cur = root;
            while (true) {
                if (p -> val < cur -> val && q -> val < cur -> val)
                    cur = cur -> left;
                else if (p -> val > cur -> val && q -> val > cur -> val)
                    cur = cur -> right;
                else return cur; 
            }
        }
    };

  • -1
    L

    Good solution! More simpler than mine.

        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    		TreeNode *node = root;
    		int pchoice, qchoice; // 0 -> left; 1 -> found; 2 -> right
    
    		while (1) {
    			if (p == node)
    				pchoice = 1;
    			else if (p->val < node->val)
    				pchoice = 0;
    			else
    				pchoice = 2;
    
    			if (q == node)
    				qchoice = 1;
    			else if (q->val < node->val)
    				qchoice = 0;
    			else
    				qchoice = 2;
    
    			if (pchoice == 1 || qchoice == 1)
    				return node;
    			else if (pchoice != qchoice)
    				return node;
    			else if (pchoice == 0)
    				node = node->left;
    			else
    				node = node->right;
    		}
    	}

  • 0

    Hi, loverszhaokai. Your code can be further shortened using conditional expressions :-)


  • 0
    L

    Yes. Thanks. Your solution is simpler.


  • 0
    N

    very very smart solution ! Thanks for sharing!


  • 1
    L
    class Solution {
    public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while((root->val-p->val)*(root->val-q->val)>0)
        	root = root->val>q->val?root->left:root->right;
        return root;
    }
    

    };


  • 0
    R

    You are awesome.


  • 0
    P

    If p or q or root equal NULL? Test cases are too kind...


  • 1

    Such cases are not very meaningful in "Lowest Common Ancestor" or related problems. The core spirit of this problem is also to grasp the recursive nature of BST and utilize it to solve the problem recursively or iteratively.


  • 1
    D

    The core spirit of coding is to make no assumption about which cases (or input) are "meaningful".


  • 1
    O

    can all the values in a BST be same?
    if it does have same values, can the algorithm work?


  • 0
    2

    @Lancelot_V this solution is so clever,i like it


  • 0
    S

    Alternative solution wich work not only for search tree:

    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            if (root == p || root == q || root == NULL) return root;
    		TreeNode *l = lowestCommonAncestor(root->left, p, q);
    		TreeNode *r = lowestCommonAncestor(root->right, p, q);
    		if (l == NULL) return r;
    		if (r == NULL) return l;
    		return root;
        }
    };
    

  • 0

  • 0
    S

    @jianchao.li.fighter said in Easy C++ Recursive and Iterative Solutions:

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (p -> val < root -> val && q -> val < root -> val)
    return lowestCommonAncestor(root -> left, p, q);
    if (p -> val > root -> val && q -> val > root -> val)
    return lowestCommonAncestor(root -> right, p, q);
    return root;
    }

    In the example given in the problem:

                    _ _ _ _ _ _ _6_ _ _ _ _ _
                   /                         \
            _ _ _ 2_ _                    _ _ _8_ _
           /          \                  /          \
           0           4                7            9
                      /  \
                     3  5
    

    The answer with @jianchao.li.fighter 's code will for p = 7 and q = 9 will be 8, is the correct answer not supposed be 6? Is 6 not the lowest common ancestor in this case?


  • 0

    @smeas https://en.wikipedia.org/wiki/Lowest_common_ancestor#/media/File:Lowest_common_ancestor.svg
    In this tree, the lowest common ancestor of the nodes x and y is marked in dark green. Other common ancestors are shown in light green.

    quoted from Wikipedia


Log in to reply
 

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