C++ Solution (Beats 90% C++ solutions)


  • 1
    S
    class Solution {
    public:
        int findNode(TreeNode* root, TreeNode* search, vector<TreeNode*> &path) {
            if (!root) {
                return 0;
            }
            
            if (root == search) {
                path.push_back(root);
                return 1;
            }
            
            int left = findNode(root->left, search, path);
            int right = findNode(root->right, search, path);
            
            if (left == 1 || right == 1) {
                path.push_back(root);
                return 1;
            }  
            
            return 0;
        }
        
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            if (!root) {
                return root;
            }
            
            // Find paths to nodes
            vector<TreeNode*> pPath;
            vector<TreeNode*> qPath;
            findNode(root, p, pPath);
            findNode(root, q, qPath);
            
            // Find where the paths diverge
            int i = pPath.size() - 1;
            int j = qPath.size() - 1;
            while (pPath[i] == qPath[j]) {
                --i;
                --j;
            }
            
            return pPath[i + 1];
        }
    };
    

Log in to reply
 

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