Considering object identity


  • 0
    G

    I opted for a (relatively) inefficient solution for the following reasons:

    • We don't know whether this BST has any duplicate elements.
    • The C++ function signature (TreeNode* root, TreeNode* p, TreeNode* q) in contrast to (TreeNode* root, int p, int q) (in addition to the above observation) suggests that object identity matters.

    Consider the following tree:

            _______6______
           /              \
        _6(a)_          ___6__
       /      \        /      \
       6(p)   _6       6       6
             /  \
             6   6(q)
    

    All nodes' values are 6, yet we are passed p and q pointing to specific nodes. The answer in this case must be exactly a and not any other 6-valued node.

    So, my algorithms consists of:

    1. Let p_path be the inclusive path from root to p, and similarly for q_path.
    2. The solution is the right-most element of the largest prefix between p_path and q_path.

    The code:

    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            auto p_path = findPath(root, p);
            auto q_path = findPath(root, q);
            
            assert(p_path.size() > 0);
            assert(q_path.size() > 0);
            assert(p_path[0] == root);
            assert(q_path[0] == root);
            assert(p_path.back() == p);
            assert(q_path.back() == q);
            
            int i = 1;
            for (; i < min(p_path.size(), q_path.size()); ++i) {
                if (p_path[i] != q_path[i]) {
                    break;
                }
            }
            
            assert(p_path[i - 1] == q_path[i - 1]);
            
            return p_path[i - 1];
        }
        
        vector<TreeNode*> findPath(TreeNode* haystack, TreeNode* needle, vector<TreeNode*> path = {}) {
            path.push_back(haystack);
            if (needle->val < haystack->val)
                return findPath(haystack->left, needle, path);
            if (needle->val > haystack->val)
                return findPath(haystack->right, needle, path);
            // so, values are equal. we must explore all equal-value nodes
            path.pop_back(); // so we don't get dupes
            return findEq(haystack, needle, path);
        }
        
        vector<TreeNode*> findEq(TreeNode* haystack, TreeNode* needle, vector<TreeNode*> path = {}) {
            path.push_back(haystack);
            if (haystack == needle) {
                return path;
            }
            if (haystack->left && haystack->left->val == needle->val) {
                auto maybe = findEq(haystack->left, needle, path);
                if (!maybe.empty())
                    return maybe;
            }
            if (haystack->right && haystack->right->val == needle->val) {
                auto maybe = findEq(haystack->right, needle, path);
                if (!maybe.empty())
                    return maybe;
            }
            return {};
        }
    };
    

Log in to reply
 

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