Given a complete binary tree, count the number of nodes.
給定一個完全二叉樹，計(jì)算其節(jié)點(diǎn)數(shù)

Definition of a complete binary tree from Wikipedia:In 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.

　　難度在于其如何優(yōu)化遞歸，縮短遞歸的次數(shù)

My Solution

(Java) Version 1 Time: Time Limit Exceeded:

　　遍歷一個樹，最先想到的方法果然是遞歸，隨手就可以寫出一個最簡單的遞歸遍歷，當(dāng)然，不出意外的話，這是一定會超時的，果然就超時了，只是寫法很容易理解，留在這里作為紀(jì)念，其次是想說，無腦沒有優(yōu)化的遞歸確實(shí)是相當(dāng)慢

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        else{
            return 1+countNodes(root.left)+countNodes(root.right);
        }
    }
}

(Java) Version 2 Time: 111ms:

　　這里真的是日了dog了，我只能說向位運(yùn)算低頭，原來用Math.pow()來計(jì)算滿二叉樹的幾點(diǎn)，然后就超時了，換成<<之后就赤果果地過了，我的天……
　　好了，說一下思路，直接遍歷每一個節(jié)點(diǎn)是不現(xiàn)實(shí)的，所以必須通過完全二叉樹的特點(diǎn)來計(jì)算，我們可以想到，除了最下的那一層，其余的部分，都是滿二叉樹，這樣我們首先可以判斷當(dāng)前的二叉樹是不是滿二叉樹，判斷的方法是判斷樹最左和最右兩邊的長度是否相等，如果相等就可以直接計(jì)算，如果不等就進(jìn)入遞歸，分別計(jì)算左右兩顆子樹，知道只有一個節(jié)點(diǎn)的時候就停止。
　　因?yàn)橥耆鏄溥M(jìn)行左右分割之后，很容易就會出現(xiàn)滿二叉樹，所以節(jié)省了大量的遍歷節(jié)點(diǎn)的時間

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int countNodes(TreeNode root) {
        int count_left = count_length_l(root);
        int count_right = count_length_r(root);
        if(root == null){
            return 0;
        }
        else{
            if(count_left == count_right){
                return (1 << count_left)-1;
            }
            else{
                return countNodes(root.left)+countNodes(root.right)+1;
            }
        }
    }

    public int count_length_l(TreeNode root){
        int count = 0;
        while(root!=null){
            count++;
            root = root.left;
        }
        return count;
    }

    public int count_length_r(TreeNode root){
        int count = 0;
        while(root!=null){
            count++;
            root = root.right;
        }
        return count;
    }
}

(Java) Version 3 Time: 79ms:

　　事實(shí)上上面那個方法就已經(jīng)過了的，不過當(dāng)時沒有想到位運(yùn)算，所以以為是遍歷的時間太長，于是重新寫了下面的這個方法，時間果然快很多，當(dāng)然如果沒有位運(yùn)算還是會超時。
　　思路是把二叉樹分為左邊一顆子樹和右邊一顆子樹，分別計(jì)算兩棵樹的最左邊，然后比較，如果相等的話，就表明左邊的子樹是滿二叉樹（是不是很巧妙），如果不等的話，就表明右邊的子樹是滿二叉樹（想一下滿二叉樹的結(jié)構(gòu)），然后分別進(jìn)入遞歸就行了，我沒有認(rèn)真計(jì)算時間復(fù)雜度，但是從巧妙程度來看應(yīng)該是比上面的方法快的

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        int count_left = count_length(root.left);
        int count_right = count_length(root.right);
        if(count_left == count_right){
            return (1 << count_left)+countNodes(root.right);
        }
        else{
            return (1 << count_right)+countNodes(root.left);
        }
    }
    
    public int count_length(TreeNode root){
        int count = 0;
        while(root!=null){
            count++;
            root = root.left;
        }
        return count;
    }
}

　　很高興的一點(diǎn)是，我自己寫的兩種遍歷方式似乎就已經(jīng)是discuss中的兩大主流方法了，基本上他們的方法也是這兩種實(shí)現(xiàn)，只是寫法有一點(diǎn)不同……所以下面貼了一個最詳細(xì)的大神的多種解法，好像挺有意思的……

(Java) Version 4 Time: 102ms (By StefanPochmann):

　　簡短一直都是推崇的原因之一

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int height(TreeNode root) {
        return root == null ? -1 : 1 + height(root.left);
    }
    public int countNodes(TreeNode root) {
        int h = height(root);
        return h < 0 ? 0 :
               height(root.right) == h-1 ? (1 << h) + countNodes(root.right)
                                         : (1 << h-1) + countNodes(root.left);
    }
}

(Java) Version 5 Time: 63ms (By StefanPochmann):

　　果然一旦擺脫了遞歸之后速度就扶搖直上，這個是一個迭代的實(shí)現(xiàn)方式，確實(shí)需要好好學(xué)習(xí)一下如何把遞歸轉(zhuǎn)化為迭代實(shí)現(xiàn)……

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int height(TreeNode root) {
        return root == null ? -1 : 1 + height(root.left);
    }
    public int countNodes(TreeNode root) {
        int nodes = 0, h = height(root);
        while (root != null) {
            if (height(root.right) == h - 1) {
                nodes += 1 << h;
                root = root.right;
            } else {
                nodes += 1 << h-1;
                root = root.left;
            }
            h--;
        }
        return nodes;
    }
}

(Java) Version 6 Time: 75ms (By StefanPochmann):

　　中間循環(huán)的實(shí)現(xiàn)原理還沒有細(xì)看，應(yīng)該是把高度方法放進(jìn)了一個方法里面，其中的整合還有待琢磨，應(yīng)該有其中的巧妙之處

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null)
            return 0;
        TreeNode left = root, 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);
    }
}