时间戳

首页 > 解决方案 > 使用根到节点路径方法超过最低共同祖先时间限制

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

问题描述

我已经实现了 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。

标签： c++treetime-complexitybinary-treelowest-common-ancestor

解决方案

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

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

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

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];
}

推荐阅读