已知一棵完全二叉树求其节点的个数

题目：已知一棵完全二叉树，求其节点的个数

要求：时间复杂度低于O（N），N为这棵树的节点个数。

分析：如果一棵树是满二叉树，高度为L，则它的节点个数是2^L-1个。

首先，遍历整棵树的左边界，因为已经告诉你这是一棵完全二叉树，你遍历它的左边界就能求出这棵树的高度，因为完全二叉树一定是从每一次的左边往右开始怼起的，怼满之后怼下一层。所以整棵树先遍历它的左边界，代价是O(logN)。然后遍历整棵树的右子树的左边界，看右子树的左边界到没到最后一层，如果到了最后一层，那么整棵树的左子树肯定是满的。右树又是一颗完全二叉树，右树的节点数就可以递归去求得。如果没到最后一层，右树就是满的，只不过左树的满和右树的满的高度不一样。

package com.tree;

public class CompleteTreeNodeNumber {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static int nodeNum(Node head) {
		if (head == null) {
			return 0;
		}
		return bs(head, 1, mostLeftLevel(head, 1));
	}

	public static int bs(Node node, int l, int h) { //node是当前节点，l指当前节点在第几层，h是一个固定的值，整棵树的深度，可以理解为一个全局变量而且永远不变，返回的是以这个node节点为头的子树一共有多少个节点
		if (l == h) { //如果来到了最后一层，node就是叶节点，所以整棵树就只有一个节点
			return 1;
		}
		if (mostLeftLevel(node.right, l + 1) == h) { //判断右子树最左的深度是否等于整棵树最深的深度
			return (1 << (h - l)) + bs(node.right, l + 1, h);
		}  //1 << (h - l)：如果右子树的左边界碰到了最后一层h，那么左子树的高度就是(h - l)，1 << (h - l)意思是2^(h-l)-1，这一部分是左树的节点个数加上当前节点之后的节点总数
		   //bs(node.right, l + 1, h):右子树又是一棵完全二叉树，递归去求它的节点个数。
	       //总体就是以node为头的完全二叉树的节点个数
		else {  //否则就是右子树的左边界没有到h，那么右树的高度比左树少一个，左树又是个完全二叉树，递归去求节点个数
			return (1 << (h - l - 1)) + bs(node.left, l + 1, h);
		}
	}

	public static int mostLeftLevel(Node node, int level) {
		while (node != null) {
			level++;
			node = node.left;
		}
		return level - 1;//返回的是整棵树最左的边界到了哪一层
	}

	public static void main(String[] args) {
		Node head = new Node(1);
		head.left = new Node(2);
		head.right = new Node(3);
		head.left.left = new Node(4);
		head.left.right = new Node(5);
		head.right.left = new Node(6);
		System.out.println(nodeNum(head));

	}

}

复杂度分析：过程中每一层只遍历一个节点，一共有O(logN)这么多层，一共也就是遍历了O(logN)这么多个节点。当遍历每个节点的时候，都会遍历一下它的右子树的左边界又是O(logN)，所以复杂度是O(（logN）^2), 非常低了。