查找二叉树高度的递归关系和时间复杂度

Question

我正在研究一个简单的问题，即在 HackerRank 上查找二叉树的高度。我下面的解决方案通过了所有测试用例，并且在手动编写一些运行代码之后，我相信它是一个 O(n) 解决方案。我在网上找到的大多数其他解决方案（我认为）也说它是 O(n)，但我无法根据这两种解决方案解决递归关系以达到 O(n)。

假设树不平衡，下面是我的解决方案：

 public static int height(Node root) {
    // Write your code here.
    if (root.left == null && root.right == null) {
      return 0;
    } else if (root.left == null && root.right != null) {
      return 1 + height(root.right);
    } else if (root.left != null && root.right == null) {
      return 1 + height(root.left);
    } else {
      return 1 + Math.max(height(root.left), height(root.right));
    }
  }

我发现调用的函数数和节点数差不多，应该是O(n)。基于我的最后一个案例，当我需要在两个分支上调用 height(node) 时，我认为这可能是最糟糕的运行时案例，我试图推导出以下递归关系

Let n be the number of nodes and k be the number of level
T(n) = 2 T(n/2)

Base Case: n = 0, n =1

T(0) = -1
T(1) = T(2^0)= 0

Recursive Case:
k = 1, T(2^1) = 2 * T(1)
k = 2, T(2^2) = 2 * T(2) = 2 * 2 * T(1) = 2^2 T(1)
k = 3, T(2^3) = 2^3 * T(1)
....
2^k = n=> k = logn => T(2^k) = 2^k * T(1) = 2^logn * T(1)

所以显然对我来说，时间复杂度是 O(2^logn)，我很困惑为什么人们说它是 O(n)？我读了这篇文章 (Is O(n) greater than O(2^log n))，我想它是有道理的，因为 O(n) > O(2^logn)，但我有两个问题：

我的递归关系和结果是否正确？如果是，为什么实际上（我计算函数被调用的次数）我仍然得到 O(n) 而不是 O(2^logn) ？
像这样的递归函数如何导出递推关系？您是否采用最坏的情况（在我的情况下是最后一个条件）并从中得出递归关系？

Answer 1

As 2^log(n) = n 根据log函数的定义，可以发现两者是一样的。这意味着 O(n) 和 O(2^log(n)) 是等价的。

另外如果需要反复求树的高度，可以对树进行预处理，将每个节点的子树高度存储起来，在预处理阶段后O(1)求树的高度。

查找二叉树高度的递归关系和时间复杂度

Recurrence Relation and Time Complexity for finding height of binary tree

algorithm

recursion

binary-tree

big-o

recurrence