Share my C++ non-recursion solution

  • 1

    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;
            if (root == node)
                return true;
            if (root->left && findNodePath(root->left, node, path) || 
                root->right && findNodePath(root->right, node, path))
                return true;
            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])
            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.