题意
计算完全二叉树节点数.
题解
不使用遍历方法, 优化时间复杂度到 O(H^2).
高度为 h 的满二叉树节点数为 2^h-1.
设计递归函数 search(Node root,int h,int H), 返回当前节点 roo 为根的完全二叉树的节点数. h 代表该节点在的高度, 高度从 1 计算, H 代表原始二叉树的高度始终不变.
t 判断当前节点的右子树的最左边的节点的高度.
- 若和该树的高度一致, 则说明左子树为满二叉树, 节点数 = 由上式得到的左子树节点数 + 本节点数 1 + 递归得到的右子树节点数.
若高度不一致, 则说明右子树为满二叉树, 节点数 = 递归得到的左子树节点数 + 1 + 上式得到的右子树节点数.
递归时间复杂度的估计: 想实际情形, 每层的节点只招一个作为根节点算子树节点数, 找当前节点右子树的最左节点需要 H, 故时间复杂度为 O(H^2).
代码
- package Tree;
- public class NodeCnt {
- public static void main(String args[]) {
- Node root=new Node(10);
- Node node1=new Node(11);
- Node node2=new Node(14);
- Node node3=new Node(11);
- Node node4=new Node(15);
- Node node5=new Node(16);
- root.left=node1;
- root.right=node2;
- node1.left=node3;
- node1.right=node4;
- node2.left=node5;
- System.out.print(nodeCnt(root));
- }
- public static int nodeCnt(Node root) {
- if(root==null) {
- return 0;
- }
- return search(root,1,mostLeftNodeH(root,1));
- }
- public static int search(Node root,int h,int H) {
- if(h==H) {
- return 1;
- }
- if(mostLeftNodeH(root.right,h+1)==H) {//
- return (1<<(H-h))+search(root.right,h+1,H);//
- }
- else {
- return (1<<(H-h-1))+search(root.left,h+1,H);
- }
- }
- public static int mostLeftNodeH(Node root,int level) {// 从原始 root
- Node node=root;
- while(node!=null) {
- ++level;
- node=node.left;
- }
- return level-1;//
- }
- }
[程序员代码面试指南] 二叉树问题 - 计算完全二叉树节点数
来源: http://www.bubuko.com/infodetail-3099933.html