Two short C++ solutions for general binary tree and BST


  • 1
    D

    The first solution works for a general binary tree where we can't rely on any ordering of the nodes:

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

    The second solution assumes a BST ordering to avoid searching much of the tree:

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

  • 0
    B

    In your second solution, I think you don't need the nested while loop. The outer while loop are already checking root->val < q->val, so on. You may use if instead of while for the nested ones.


Log in to reply
 

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