自媒体还是做网站,常德县,创建网站的免费软件国内,肇庆做网站的公司完全二叉树的节点个数
你一棵 完全二叉树 的根节点 root #xff0c;求出该树的节点个数。
完全二叉树 的定义如下#xff1a;在完全二叉树中#xff0c;除了最底层节点可能没填满外#xff0c;其余每层节点数都达到最大值#xff0c;并且最下面一层的节点都集中在该层最…完全二叉树的节点个数
你一棵 完全二叉树 的根节点 root 求出该树的节点个数。
完全二叉树 的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层则该层包含 1~ 2h 个节点。
示例 1 输入 root [1,2,3,4,5,6] 输出 6
解题思路
树的高度
计算树的高度可以在 O(log n) 时间内完成通过沿着左子树一直走到底。
完全二叉树的性质
对于完全二叉树如果左右子树的高度相同那么左子树一定是满二叉树可以直接计算其节点数如果左右子树的高度不同那么右子树一定是满二叉树。
递归计算
根据左右子树的高度关系递归地计算左右子树的节点数直到叶节点。
Java实现
public class CountNodes {public static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val x; }}/** 二叉树的节点数 */public int countNodes(TreeNode root) {if (root null) {return 0;}int leftDepth computeDepth(root.left);int rightDepth computeDepth(root.right);if (leftDepth rightDepth) {// 左子树是满二叉树return (1 leftDepth) countNodes(root.right);} else {// 右子树是满二叉树return (1 rightDepth) countNodes(root.left);}}/** 二叉树的深度 */private int computeDepth(TreeNode node) {int depth 0;while (node ! null) {node node.left;depth;}return depth;}public static void main(String[] args) {CountNodes countNodes new CountNodes();// 构建示例完全二叉树TreeNode root new TreeNode(1);root.left new TreeNode(2);root.right new TreeNode(3);root.left.left new TreeNode(4);root.left.right new TreeNode(5);root.right.left new TreeNode(6);// 计算完全二叉树的节点个数int result countNodes.countNodes(root);System.out.println(Number of nodes: result); // 输出: 6}
}
时间空间复杂度
时间复杂度O(log n * log n)每次递归调用都减少一半节点递归的次数logn且需要计算树的高度logn。空间复杂度O(log n)递归栈的深度等于树的高度。
