LeetCode222 完全二叉树节点数

题目

传送门

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

这个需求的暴力解法是遍历一遍,时间复杂度 $O(N)$ 尚可接受,但这样就失去了这题的意义。这里实现一个时间复杂度为 $O( \log_2 N)$ 的算法。

计算上部节点数

不难得出以下结论:

  • 第 h 层的节点数为 $2^{h-1}$ (h 从 1 开始)
  • 从根节点到第 h 层总节点数为 $2^h-1$(h 从 1 开始)

那么只要知道了树的高度,就可以立即求出除了最后一层外的节点总数。同时鉴于完全二叉树的特性,只需一直向左子树遍历就可以得到高度。

1
2
3
4
5
6
7
8
9
// 求完全二叉树的高度
private int height(TreeNode root) {
  int res = 0;
  while (root != null) {
    res++;
    root = root.left;
  }
  return res;
}

计算底层节点数

寻找最后一个节点

如图所示,我们给底层节点编号(包括不存在的节点),形式上把它们视为有序数组。也就是说,只需在 $O( \log_2 N)$ 时间复杂度内从这个数组中找到最后一个存在的节点就行。这个需求很轻松地联想到二分查找。

不过需要对二分查找做一点修改:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
private int findLastNodeIndex(TreeNode root, int height) {
  int l = 0, r = (int) (Math.pow(2, height - 1) - 1); // 搜索区间为 [l,r]
  while (l < r) {
    int mid = (int) Math.ceil((l + r) / 2f); // 向上取整
    if (nodeExists(root, height, mid))
      l = mid;
    else
      r = mid - 1;
  }
  return l;
}

计算中间下标时为什么向上取整? 在本题的场景下,二分查找最终一定会收缩到两个相邻的节点,如果我们向下取整,那么就无从得知右边的节点是否存在(除非编写额外的代码)。如果向上取整的话,即使节点不存在,也可以自然地回退到左边的节点。

为什么收缩左边界时不需要 mid+1,但收缩右边界时却是 mid-1 我们要找的是最右边的节点。因此收缩左边界是要留有一个保底项。否则可能有这样一个情况:当前的 mid 已经是最右边的节点了,那么之后的查找都会失败,还得编写额外的代码记录 mid,以便后续查找失败时回退。

既然搜索区间是 [l,r] 闭区间,为什么循环条件不是 l<=r 按照典型二分查找算法,当搜索区间为闭区间时,l==r 是有意义的,此时 l 就是要找的元素。在这里也不例外。不过因为上边提到的收缩左边界的改进,导致可能出现死循环,那么就得额外加一条判断跳出循环,最终和这么写的等价的。

通过下标寻找节点

二分查找要求可以通过下标来找到元素,显然二叉树不满足这个要求,还得编写额外的函数来实现。

我们可以把整个二叉树看作是一个标准二分查找的执行过程。现在知道了目标节点的下标,只需把它和当前搜索区间的中点进行对比,再决定往左还是往右查找就行了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// 判断最后一层下标为 index 的节点是否存在
private boolean nodeExists(TreeNode root, int height, int index) {
  int l = 0, r = (int) (Math.pow(2, height - 1) - 1);
  for (int level = 0; level < height - 1; level++) {
    int mid = (int) Math.ceil((l + r) / 2f);
    if (index >= mid) {
      root = root.right;
      l = mid;
    } else {
      root = root.left;
      r = mid - 1;
    }
  }
  return root != null;
}

代码(java)

时间复杂度分析:

  • 求树高的时间复杂度为 $O(\log N)$
  • 最后一层最多有 $2^{h-1}$ 个节点,它几乎是总节点数的一半。同时考虑二分算法,可得出寻找最后一个节点的时间复杂度为 $\log {N/2} = O(\log N)$
  • 寻找最后一个节点时,每一次利用下标取节点的时间复杂度均为 $O(h) = O(\log N)$

因此总体时间复杂度为 $O(\log N + \log^2 N)) = O(\log^2 N)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int height = height(root);
        // 忽略最后一层的节点数
        int upperCount = (int) (Math.pow(2, height - 1) - 1);
        return upperCount + findLastNodeIndex(root, height) + 1;
    }

    private int height(TreeNode root) {
        int res = 0;
        while (root != null) {
            res++;          root = root.left;
        }
        return res;
    }

    // 寻找最后一层最右边节点的下标。
    private int findLastNodeIndex(TreeNode root, int height) {
        int l = 0, r = (int) (Math.pow(2, height - 1) - 1);
        while (l < r) {
            int mid = (int) Math.ceil((l + r) / 2f);
            if (nodeExists(root, height, mid))
                l = mid;
            else
                r = mid - 1;
        }
        return l;
    }

    // 判断最后一层下标为 index 的节点是否存在
    private boolean nodeExists(TreeNode root, int height, int index) {
        int l = 0, r = (int) (Math.pow(2, height - 1) - 1);
        for (int level = 0; level < height - 1; level++) {
            int mid = (int) Math.ceil((l + r) / 2f);
            if (index >= mid) {
                root = root.right;
                l = mid;
            } else {
                root = root.left;
                r = mid - 1;
            }
        }
        return root != null;
    }
}
禁止转载到私域(公众号,非自己托管的博客等),其他情况请注明原作者与可点击跳转的来源链接。