Leetcode -- 222. Count Complete Tree Nodes

https://leetcode.com/problems/count-complete-tree-nodes/

解法II：Recursion

如果当前子树的“极左节点”（从根节点出发一路向左）与“极右节点”（从根节点出发一路向右）的高度h相同，则当前子树为满二叉树，返回2^h - 1

否则，递归计算左子树与右子树的节点个数。

注意：2^h ==> (int)Math.pow(2,h) or (2>>(h-1))or(1>>h)//shift is after '-','+'

In the worst case, you will have to keep making recursive calls to the bottom-most leaf nodes (e.g. last level only have one single node). So you end up calling countNodes() h times. Each time, you will have to do traversals along the left and right edges. At level h, you iterate zero times (no child). At level h - 1, you iterate once (one child). And so on. So that is 0 + 1 + 2 + ... + h steps just to compute the left edges, which is h(1 + h)/2 = O(h^2).

The space complexity will just be the size of the call stack, which is O(h).

 

public class Solution {
    public int countNodes(TreeNode root) {
        if(root==null)return 0;
 
        int left = getLeftHeight(root)+1;    
        int right = getRightHeight(root)+1;
 
        if(left==right){
            return (1<<left)-1;//(int)Math.pow(2,left) will exceed time limit 
        }else{
            return countNodes(root.left)+countNodes(root.right)+1;
        }
        
    }
    public int getLeftHeight(TreeNode root){
        if(root==null)return 0;//recur即 return root == null ? -1 : 1 + height(root.left);
        int height = 0;
        while(root.left!=null){
            height++;
            root=root.left;
        }
        return height;
    }
    public int getRightHeight(TreeNode root){
        if(root==null)return 0;
        int height = 0;
        while(root.right!=null){
            height++;
            root=root.right;
        }
        return height;
    }
}