Simple C++ solution, easy to understand


  • 5
    I
    vector<TreeNode*> path, path1, path2;
    
    void find_in_tree(TreeNode *root, TreeNode *p, TreeNode *q) {
        if (!root) return;
        path.push_back(root);
        if (root == p) {
            path1 = path;
        } else if (root == q) {
            path2 = path;
        }
        find_in_tree(root->left, p, q);
        find_in_tree(root->right, p, q);
        path.pop_back();
    }
    
    TreeNode* lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        find_in_tree(root, p, q);
        int min_size = min(path1.size(), path2.size());
        for (int i = 0; i < min_size; i++) {
            if (path1[i] != path2[i]) return path1[i - 1]; 
        }
        return path1[min_size - 1];
    }

Log in to reply
 

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