0

-- 下面的函数在二叉树中lowestCommonAncestor找到两个节点的最低共同祖先p和（假设两个节点都存在并且所有节点值都是唯一的）。q

class Solution {
public:

    bool inBranch(TreeNode* root, TreeNode* node)
    {
        if (root == NULL)
            return false;

        if (root->val == node->val)
            return true;

        return (inBranch(root->left, node) || inBranch (root->right, node));
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        if (root == NULL)
            return NULL;

        if (root->val == p->val || root->val == q->val)
            return root;

        bool pInLeftBranch = false;
        bool qInLeftBranch = false;

        pInLeftBranch = inBranch (root->left, p);
        qInLeftBranch = inBranch (root->left, q);

        //Both nodes are on the left
        if (pInLeftBranch && qInLeftBranch)
            return lowestCommonAncestor(root->left, p, q);
        //Both nodes are on the right
        else if (!pInLeftBranch && !qInLeftBranch)
            return lowestCommonAncestor(root->right, p, q);
        else 
            return root;

    }
};
4

2 回答 2

2

每次调用时inBranch(root, node)，都会添加 O(# of descendents of root)（参见二叉树搜索的时间复杂度）。我将假设二叉树在第一次计算时间复杂度时是平衡的，然后看一下树不平衡的最坏情况。

场景一：平衡树

一个节点的后代数量大约是其父节点的一半。因此，每次我们递归时，调用的inBranch成本将减半。假设 N 是树中的节点总数。在第一次调用中lowestCommonAncestor，我们搜索所有 N 个节点。在随后的调用中，我们搜索左半部分或右半部分，依此类推。

O(N + N/2 + N/4 ...)仍然与 O(N) 相同。

场景 2：不平衡树

假设这棵树非常不平衡，所有孩子都在左侧：

     A
    /
   B
  /
 C
/
etc...

对于每个递归级别，后代的数量仅减少 1。因此，我们的时间复杂度类似于：

O(N + (N-1) + (N-2) + ... + 2 + 1)相当于 O(N^2)。

有没有更好的办法？

如果这是一个二叉搜索树，我们可以做得和 O(path_length(p) + path_length(q)) 一样好。如果没有，您将始终需要至少遍历整个树一次：O(N) 来找到每个节点的路径，但您仍然可以改善最坏的情况。我会留给你找出实际的算法！

于 2018-07-12T14:37:28.823 回答
1

在最坏的情况下，二叉树是一个长度列表，N其中每个节点最多有一个子节点，而p和q是相同的叶节点。在这种情况下，您将有一个运行时间：您在树下的每个节点上O(N^2)调用inBranch(runtime )。O(N)

如果二叉树是平衡的，这将变成节点O(N log(N))，N因为您可以将O(2^K)节点放入深度树中K（并且在大多数情况下递归K）：找到每个节点是O(N)，但您最多只能执行log(N)一次。 检查本琼斯的答案！

请注意，更好的算法将定位每个节点一次并存储树下的路径列表，然后比较路径。找到树中的每个节点（如果它是未排序的）必然是最坏的情况O(N)，列表比较也是O(N)（不平衡情况）或O(log(N))（平衡情况）所以总运行时间是O(N)。你可以在排序树上做得更好，但这显然不是这里给定的。

于 2018-07-12T14:20:35.243 回答