Share my C++ non-recursion solution


  • 1
    N

    The main idea is to find the two paths : root ->...-> p, root ->...-> q, then the last same node is LCA.

        
        bool findNodePath(TreeNode* root, TreeNode* node, vector<TreeNode*>& path)
        {
            if (root == NULL)
                return false;
            
            path.push_back(root);
            
            if (root == node)
                return true;
            
            if (root->left && findNodePath(root->left, node, path) || 
                root->right && findNodePath(root->right, node, path))
                return true;
            
            path.pop_back();
            return false;
        }
    
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
        {
            if (root == NULL || root == p || root == q) return root;
            // O(n) extra space
            vector<TreeNode*> path_p;
            vector<TreeNode*> path_q;
            findNodePath(root, p, path_p);
            findNodePath(root, q, path_q);
            
            int i = 0;
            for ( ; i < path_p.size() && i < path_q.size(); ++i)
                if (path_p[i] != path_q[i])
                    break;
            return path_p[i - 1];
        }
    

Log in to reply
 

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