展示型网站建设方案书,wordpress the id,网站首页地址是什么,零基础考二建有多难目录 完全二叉树 LeetCode 222. 完全二叉树的节点个数
完全二叉树
作者#xff1a;labuladong
如何求一棵完全二叉树的节点个数呢#xff1f;
// 输入一棵完全二叉树#xff0c;返回节点总数
int countNodes(TreeNode root);如果是一个普通二叉树#xff0c;显然只要向… 目录 完全二叉树 LeetCode 222. 完全二叉树的节点个数
完全二叉树
作者labuladong
如何求一棵完全二叉树的节点个数呢
// 输入一棵完全二叉树返回节点总数
int countNodes(TreeNode root);如果是一个普通二叉树显然只要向下面这样遍历一边即可时间复杂度 O(N)
public int countNodes(TreeNode root) {if (root null) return 0;return 1 countNodes(root.left) countNodes(root.right);
}如果是一棵满二叉树节点总数就和树的高度呈指数关系
public int countNodes(TreeNode root) {int h 0;// 计算树的高度while (root ! null) {root root.left;h;}// 节点总数就是 2^h - 1return (int)Math.pow(2, h) - 1;
}
完全二叉树比普通二叉树特殊但又没有满二叉树那么特殊计算它的节点总数可以说是普通二叉树和完全二叉树的结合版
判断当前节点引导的子树是不是满二叉是的话可以直接返回子树结点数不是的话就往下遍历。由于完全二叉树的性质左右子树中最多只有一个子树不是满二叉。所以总体的时间复杂度仍然是logn ^ 2。
public int countNodes(TreeNode root) {TreeNode l root, r root;// 沿最左侧和最右侧分别计算高度int hl 0, hr 0;while (l ! null) {l l.left;hl;}while (r ! null) {r r.right;hr;}// 如果左右侧计算的高度相同则是一棵满二叉树if (hl hr) {return (int)Math.pow(2, hl) - 1;}// 如果左右侧的高度不同则按照普通二叉树的逻辑计算return 1 countNodes(root.left) countNodes(root.right);
}开头说了这个算法的时间复杂度是 O(logN*logN)这是怎么算出来的呢
直觉感觉好像最坏情况下是 O(N*logN) 吧因为之前的 while 需要 logN 的时间最后要 O(N) 的时间向左右子树递归
return 1 countNodes(root.left) countNodes(root.right);关键点在于这两个递归只有一个会真的递归下去另一个一定会触发 hl hr 而立即返回不会递归下去。
为什么呢原因如下
一棵完全二叉树的两棵子树至少有一棵是满二叉树 由于完全二叉树的性质其子树一定有一棵是满的所以一定会触发 hl hr只消耗 O(logN) 的复杂度而不会继续递归。
综上算法的递归深度就是树的高度 O(logN)每次递归所花费的时间就是 while 循环需要 O(logN)所以总体的时间复杂度是 O(logN*logN)。
所以说「完全二叉树」这个概念还是有它存在的原因的不仅适用于数组实现二叉堆而且连计算节点总数这种看起来简单的操作都有高效的算法实现。
