LC 222 Count Complete Tree Nodes(M)

Given a complete binary tree, count the number of nodes.

Complet Binary Tree definition: n a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

public int countNodes(TreeNode root)

边界条件 如果root=null 结果是0.

解题思路 优化的递归算法

如果采用简单的递归统计所有Node，时间可能超界， 根据完全二叉树特性， 比较最左边 和最右边的Node, 如果等高，表示是个完整二叉树，节点和是 2的h次方 - 1, 程序写法是 1<<height - 1; 如果不等高，递归法去计算左右树的节点和 ＋ 1

public int countNodes(TreeNode root) {
    if (root == null)
        return 0;
    TreeNode left = root;
    TreeNode right = root;
    int height = 0;
    while(right != null){
        left = left.left; //最左节点
        right = right.right; //最右节点
        //统计高度
        height++;
    }
    if(left == null){
        //完整二叉树
        return (1<<height) - 1;
    }
    return 1 + countNodes(root.left) + countNodes(root.right);
}