有特点的个人网站,网络营销的七种方法,自己建的网站搜不到,做玩具什么 网站比较好222. 完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root #xff0c;求出该树的节点个数。
完全二叉树 的定义如下#xff1a;在完全二叉树中#xff0c;除了最底层节点可能没填满外#xff0c;其余每层节点数都达到最大值#xff0c;并且最下面一层的节点都集中…222. 完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root 求出该树的节点个数。
完全二叉树 的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层则该层包含 1 ∼ 2 h 1 \sim 2^h 1∼2h 个节点。
示例 1 输入 root [1,2,3,4,5,6] 输出 6 示例 2 输入 root [] 输出 0 示例 3 输入 root [1] 输出 1 提示
树中节点的数目范围是 [ 0 , 5 × 1 0 4 ] [0, 5 \times 10^4] [0,5×104] 0 ≤ N o d e . v a l ≤ 5 ∗ 104 0 \leq Node.val \leq 5 * 104 0≤Node.val≤5∗104题目数据保证输入的树是 完全二叉树
进阶 遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗
解法一(统一迭代遍历)
思路分析 采用统一迭代二叉树的遍历方法来对二叉树进行遍历在遍历的过程中统计节点数目 此处采用 前序遍历
实现代码如下
class Solution {public int countNodes(TreeNode root) {int ans 0;if (root null)return ans; // 边界条件DequeTreeNode stack new LinkedList();stack.push(root);while (!stack.isEmpty()) {TreeNode node stack.pop();if (node ! null) {// 对节点进行处理 添加待遍历节点if (node.right ! null)stack.push(node.right);if (node.left ! null)stack.push(node.left);// 添加待处理节点stack.push(node);stack.push(null); // 使用null标记待处理节点} else {stack.pop(); // 弹出待处理节点 ans; // 对节点进行计数}}return ans;}}return ans;}
}提交结果如下 解答成功: 执行耗时:9 ms,击败了5.25% 的Java用户 内存消耗:44.5 MB,击败了83.97% 的Java用户 复杂度分析
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n ) O(n) O(n)
解法二(BFS队列)
思路分析
采用层序遍历法对二叉树进行遍历并在遍历过程中 统计节点数
实现代码如下
class Solution {// BFSpublic int countNodes(TreeNode root) {int ans 0;if (root null)return ans; // 边界条件QueueTreeNode queue new ArrayDeque();queue.offer(root);while (!queue.isEmpty()) {int size queue.size();for (int i 0; i size; i) { ans;TreeNode node queue.poll();if (node.left ! null) queue.offer(node.left);if (node.right ! null) queue.offer(node.right);}}return ans;}
}提交结果如下 解答成功: 执行耗时:5 ms,击败了9.04% 的Java用户 内存消耗:46.5 MB,击败了5.07% 的Java用户 复杂度分析
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n ) O(n) O(n)
解法三(二分查找位运算)
思路分析 首先题目给出该二叉树为 完全二叉树因此可以利用完全二叉树的特性计算节点个数。 首先规定根节点位于第0层完全二叉树的最大层数为h且根据完全二叉树的特性有最左边的节点一定位于最底层且从根节点到最左边的节点的路径长度即为最大层数h 当 0 ≤ i h 0 \leq i h 0≤ih时第i层包含 2 i 2^i 2i个节点最底层包含节点数最少为1最多为 2 h 2^h 2h 当底层包含1个节点时完全二叉树的节点个数是 ∑ i 0 h − 1 2 i 1 2 h \sum_{i0}^{h-1}2^i1 2^h ∑i0h−12i12h 当底层包含 2 h 2^h 2h个节点时完全二叉树的节点个数时 ∑ i 0 h 2 h 1 − 1 \sum_{i0}^{h} 2^{h1} - 1 ∑i0h2h1−1 因此对于最大层数为h的完全二叉树节点个数在 [ 2 h , 2 h 1 − 1 ] [2^h, 2^{h1}-1] [2h,2h1−1]的范围内即在该范围内通过二分查找的方式得到完全二叉树的节点个数 即根据节点个数范围的上下界得到判断的节点个数k如果第k个节点存在则节点个数一定大于或等于k如果第k个节点不存在则节点个数一定小于 k因此每次查找的范围缩小一半直到找到节点个数。 如何判断第k个节点是否存在如果第k个节点位于第h层则k的二进制表示包含h1位且最高位为1其余各位从高到底表示从根节点到第k个节点的路径0表示移动到左子节点1表示移动到右子节点 通过位运算得到第k个节点对应的路径然后判断该路径对应的节点是否存在则可判断第k个节点是否存在
实现代码如下
class Solution {// 二分查找 位运算public int countNodes(TreeNode root) {if (root null) return 0; // 边界// 获取二叉树的层数int h 0;TreeNode node root;while (node.left ! null) { h; // 计算二叉树的层数node node.left;}// 根据二叉树的层数 获取节点数范围int min 1 h; // 位运算计算 最低限度int max (1 (h 1)) - 1; // 位运算计算 最高限度int ans 0; // 即二分查找寻找符合条件的 用ans来保存// 二分查找区间为 左闭右闭while (min max) {int mid ((max - min) 1) min;if (exitTreeNode(mid, root, h)) {// 如果存在 则继续查找ans mid;min mid 1;} else {max mid - 1;}}return ans; // 在结束二分查找时 min指向的节点是最后一个存在的节点}private boolean exitTreeNode(int k, TreeNode root, int level) {// 获取当前从根节点出发的方向int bits 1 (level-1);TreeNode node root;while (node ! null bits 0) {if ((bits k) 0) {node node.left;} else {node node.right;}bits 1;}return node ! null;}
}提交结果如下 解答成功: 执行耗时:0 ms,击败了100.00% 的Java用户 内存消耗:46.4 MB,击败了8.84% 的Java用户 复杂度分析
时间复杂度 O ( l o g 2 n ) O(log^{2}_{}{n}) O(log2n)n为完全二叉树的节点数空间复杂度 O ( 1 ) O(1) O(1)只使用有限的额外空间
