nc84. 求完全二叉树的高度

1. 思路一: (暴力做法, 不合要求)

直接递归统计二叉树的节点个数即可.

空树没有节点, 加上左子树和右子树的节点数就可以.

class Solution {
public:
    int nodeNum(struct TreeNode* head) {
        if (!head) return 0; // 空树没有节点
        int res = 1; // 根节点非空, 算1个
        // 递归加上左右孩子, 不用判空
        res += nodeNum(head->left);
        res += nodeNum(head->right);
        return res;
    }
};
  • 时间复杂度: 因为每个节点都遍历了一遍,所以对于n个节点的树,时间复杂度是O(n).
  • 空间复杂度: 同理,每一个节点都调用了一次nodeNum函数, 所以空间复杂度也是O(n).

2. 思路二: (利用完全二叉树的性质)

思路一没有用到完全二叉树这个条件, 时间复杂度也是不合要求的,那么我们看下如何利用这个条件进行优化.

这里我们复习一下完全二叉树的性质:

图片说明

完全二叉树的定义:

对于一个树高为h的二叉树，如果其第0层至第h-1层的节点都满。如果最下面一层节点不满，则所有的节点在左边的连续排列，空位都在右边。这样的二叉树就是一棵完全二叉树。

完全二叉树有以下特点:

  • 可能是一个空树.
  • 它的倒数第二层及以上都是“铺满”的, 叶子节点只能在最后两层.
  • 它的左右两个孩子中, 必有一个是满二叉树, 且另一个子树也是完全二叉树.

那么本题中, 我们会用到第三个性质. 若知道一个高度为n的树是满二叉树, 我们可以直接算出它的节点数是(1<<n)-1, 且n的计算是对数复杂度的. 那么问题的关键就在于如何以O(logn)的复杂度算出树的高度. 因为我们知道了左右子树的高度, 分别记为lh和rh, 就可以这样推导了:

  • 若lh==rh, 说明左子树一定是满二叉树了, 那么递归计算右边就可以了.
  • 若lh!=rh, 说明右子树一定是满二叉树了, 那么递归计算左边.

接下来就是求树高度, 这个很简单, 只需要一直往左边迭代即可, 根据完全二叉树的性质, 不可能出现“缺左” 的情形.

接下来实现就可以了

class Solution {
public:
    int nodeNum(struct TreeNode* head) {
        if (!head) return 0; // 空树算0个
        // 计算左右孩子, 不用判空, 如果left或right为空, 函数返回0
        int lh = getHeight(head->left), rh = getHeight(head->right);

        int res = 1; // 根节点算1个
        if (lh == rh) {
            // (1<<lh) - 1 是左子树满二叉树的节点数, 右子树一定也是完全二叉树, 故递归计算
            res += nodeNum(head->right) + (1<<lh) - 1;
        } else {
            // 同上, 右子树一定是满二叉树
            res += nodeNum(head->left) + (1<<rh) - 1;
        }
        return res;
    }

    int getHeight(struct TreeNode* head) {
        int h = 0; // 初始高度是0
        while (head) {
            h++; // 当前节点存在, 高度加1
            head = head->left; // 向左走
        }
        return h;
    }
};
  • 时间复杂度: 对节点数为n的二叉树, 很容易看出getHeight的复杂度为O(logn), nodeNum每次递归的时候, 高度减一, 调用常数次getHeight, 而高度为logn, 故总的时间复杂度是O((logn)^2)
  • 空间复杂度: 对节点数为n的二叉树, 每一层递归计算一次, 最多递归计算logn轮, 每一轮递归都是常数空间, 因此空间复杂度为O(logn).