使用根到节点路径方法超过最低公共祖先时间限制

Question

我已经实现了 LCA 问题的解决方案。问题陈述是给定一棵二叉树，找到树中两个给定节点的最低公共祖先 (LCA)。我使用的方法是找到从根到给定 2 个节点的路径，并将这 2 个路径存储在一个向量中。从根开始比较两条路径中的节点（直到 LCA 的路径应该匹配 p 和 q），因此，路径中发生不匹配之前的节点将是 LCA。

但是 Leetcode 中仅 29/31 个测试用例就通过了，对于非常大的输入，超过了时间限制。这是代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> path;
    void pathUntilNode(TreeNode* root, vector<TreeNode*> res, TreeNode* p){
        if(root==NULL) return;
        res.push_back(root);
        if(root==p){
            path=res;
            return ;
        }
        pathUntilNode(root->left, res, p);
        pathUntilNode(root->right, res, p);
    }
    
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL) return NULL;
        vector<TreeNode*> res;
        pathUntilNode(root, res, p);
        vector<TreeNode*> path1 = path;
        pathUntilNode(root, res, q);
        vector<TreeNode*> path2 = path;
        int i;
        for(i=0;i<min(path1.size(),path2.size());i++){
            if(path1[i]!=path2[i])
                return path1[i-1];
        }
        return path1[i-1];
    }  
};

据我所知时间复杂度是O(N)。不明白为什么我会得 TLE。

Answer 1

问题是您的代码使所有向量指针都引用相同向量。但是你需要 path1 和 path2 是单独的向量。因此，如果在执行 path = res 之后您还有另一个 res.push_back(root)，这将影响 path，它已成为 res 的同义词...

其次，即使找到匹配项，您的递归搜索仍会继续搜索。这是浪费时间。它应该尽快退出递归树。因此，如果它从节点的左子节点中搜索返回 - 它找到了匹配项 - 它不应该继续在节点的右子节点中搜索。

有几种方法可以解决第一个问题，但本质上这两条路径必须是单独的向量。一种方法是使递归函数 return 成为路径（如果找到则为空）。这样路径将反向构建，但这很容易解决：

vector<TreeNode*> notfound;

vector<TreeNode*> pathUntilNode(TreeNode* root, TreeNode* p) {
    if (root == NULL) return notfound;
    if (root == p) return { root }; // found: start a new path
    vector<TreeNode*> path = pathUntilNode(root->left, p);
    // only look in the other subtree if no success yet...
    if (path == notfound) path = pathUntilNode(root->right, p);
    if (path != notfound) path.push_back(root);  // success: extend the path
    return path;
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    vector<TreeNode*> path1 = pathUntilNode(root, p);
    vector<TreeNode*> path2 = pathUntilNode(root, q);
    reverse(path1.begin(), path1.end());
    reverse(path2.begin(), path2.end());
    // no change below this point
    int i;
    for (i = 0; i < min(path1.size(), path2.size()); i++) {
        if (path1[i] != path2[i])
            return path1[i-1];
    }
    return path1[i-1];
}

使用根到节点路径方法超过最低公共祖先时间限制

Lowest Common Ancestor Time Limit Exceeded using the root to node path approach

c++

tree

binary-tree

time-complexity

lowest-common-ancestor