java - 无法理解 TreeNode 中的 Big-O

Question

我无法理解 Big O 问题。

问题

public boolean isHB(TreeNode root){
    if (root==null)
        return tree;
    int heightL = height(root.left);
    int heightR = height(root.right);
    boolean leftHB = isHB(root.left);
    boolean rightHB = isHB(root.right);
    if (Math.abs(heightL-heightR)>1)
        return false;
    return leftHB && rightHB;
}

1/假设树是高度平衡的。找到 Big O，其中 n 是树中的节点数。

2/不要假设树是高度平衡的。找到 Big O，其中 n 是树中的节点数。

我不明白

1/解为:2T(2/n) + O(n) = O(n log(n))。我知道 2T(2/n) 来自哪里，但我无法弄清楚 O(n) 来自哪里。

2/解为:T(n-1) + O(n) = O(n^2)。在这种情况下，由于树不平衡，我理解 T(n-1)，但我仍然无法弄清楚 O(n) 从何而来。

Answer 1

查找树的高度的复杂度为 O(n)。所以额外的部分是求高度的复杂性。