摘要：如果不等于，則是左子樹(shù)的節(jié)點(diǎn)數(shù)，加上右子樹(shù)的節(jié)點(diǎn)數(shù)，加上自身這一個(gè)。注意這里在左節(jié)點(diǎn)遞歸時(shí)代入了上次計(jì)算的左子樹(shù)最左深度減，右節(jié)點(diǎn)遞歸的時(shí)候代入了上次計(jì)算的右子樹(shù)最右深度減，可以避免重復(fù)計(jì)算這些深度做的冪時(shí)不要用，這樣會(huì)超時(shí)。

Given a complete binary tree, count the number of nodes.
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.

時(shí)間 O(N) 空間 O(1)

完全二叉樹(shù)的一個(gè)性質(zhì)是，如果左子樹(shù)最左邊的深度，等于右子樹(shù)最右邊的深度，說(shuō)明這個(gè)二叉樹(shù)是滿(mǎn)的，即最后一層也是滿(mǎn)的，則以該節(jié)點(diǎn)為根的樹(shù)其節(jié)點(diǎn)一共有2^h-1個(gè)。如果不等于，則是左子樹(shù)的節(jié)點(diǎn)數(shù)，加上右子樹(shù)的節(jié)點(diǎn)數(shù)，加上自身這一個(gè)。

這里在左節(jié)點(diǎn)遞歸時(shí)代入了上次計(jì)算的左子樹(shù)最左深度減1，右節(jié)點(diǎn)遞歸的時(shí)候代入了上次計(jì)算的右子樹(shù)最右深度減1，可以避免重復(fù)計(jì)算這些深度

做2的冪時(shí)不要用Math.pow，這樣會(huì)超時(shí)。用1<

public class Solution {
    public int countNodes(TreeNode root) {
        return countNodes(root, -1, -1);
    }
    
    private int countNodes(TreeNode root, int lheight, int rheight){
        // 如果沒(méi)有上輪計(jì)算好的左子樹(shù)深度，計(jì)算其深度
        if(lheight == -1){
            lheight = 0;
            TreeNode curr = root;
            while(curr != null){
                lheight++;
                curr = curr.left;
            }
        }
        // 如果沒(méi)有上輪計(jì)算好的右子樹(shù)深度，計(jì)算其深度
        if(rheight == -1){
            rheight = 0;
            TreeNode curr = root;
            while(curr != null){
                rheight++;
                curr = curr.right;
            }
        }
        // 如果兩個(gè)深度一樣，返回2^h-1
        if(lheight == rheight) return (1 << lheight) - 1;
        // 否則返回左子樹(shù)右子樹(shù)節(jié)點(diǎn)和加1
        return 1 + countNodes(root.left, lheight - 1, -1) + countNodes(root.right, -1, rheight - 1);
    }
}

時(shí)間 O(N) 空間 O(1)

用迭代法的思路稍微有點(diǎn)不同，因?yàn)椴辉偈沁f歸中那樣的分治法，我們迭代只有一條正確的前進(jìn)方向。所以，我們判斷的時(shí)左節(jié)點(diǎn)的最左邊的深度，和右節(jié)點(diǎn)的最左邊深度。因?yàn)樽詈笠粚咏Y(jié)束的地方肯定在靠左的那側(cè)，所以我們要找的就是這個(gè)結(jié)束點(diǎn)。如果兩個(gè)深度相同，說(shuō)明左子樹(shù)和右子樹(shù)都是滿(mǎn)，結(jié)束點(diǎn)在右側(cè)，如果右子樹(shù)算出的最左深度要小一點(diǎn)，說(shuō)明結(jié)束點(diǎn)在左邊，右邊已經(jīng)是殘缺的了。根據(jù)這個(gè)大小關(guān)系，我們可以確定每一層的走向，最后找到結(jié)束點(diǎn)。另外，還要累加每一層的節(jié)點(diǎn)數(shù)，最后如果找到結(jié)束點(diǎn)，如果結(jié)束點(diǎn)是左節(jié)點(diǎn)，就多加1個(gè)，如果結(jié)束點(diǎn)是右節(jié)點(diǎn)，就多加2個(gè)。

同樣的，記錄上次計(jì)算的最左深度，可以減少一些重復(fù)計(jì)算

用int記錄上次最左深度更快，用Integer則會(huì)超時(shí)

未優(yōu)化版本

public class Solution {
    public int countNodes(TreeNode root) {
        int res = 0;
        Integer lheight = null, rheight = null;
        while(root != null){
            // 得到左節(jié)點(diǎn)的最左深度
            int leftH = getH(root.left);
            // 得到右節(jié)點(diǎn)的最左深度
            int rightH = getH(root.right);
            // 左節(jié)點(diǎn)的最左深度大，說(shuō)明右邊已經(jīng)殘缺，結(jié)束點(diǎn)在左邊
            if(leftH > rightH){
                if(rightH != 0) res += 1 << rightH;
                else return res + 2;
                root = root.left;
            // 否則說(shuō)明結(jié)束點(diǎn)在右邊
            } else {
                if(leftH != 0) res += 1 << leftH;
                else return res + 1;
                root = root.right;
            }
        }
        return res;
    }
    
    private int getH(TreeNode root){
        int h = 0;
        while(root != null){
            ++h;
            root = root.left;
        }
        return h;
    }
}

public class Solution {
    public int countNodes(TreeNode root) {
        int res = 0;
        int lheight = -1, rheight = -1;
        while(root != null){
            // 如果沒(méi)有上次記錄的左邊最左深度，重新計(jì)算
            if(lheight == -1){
                TreeNode curr = root.left;
                lheight = 0;
                while(curr != null){
                    curr = curr.left;
                    lheight++;
                }    
            }
            // 如果沒(méi)有上次記錄的右邊最左深度，重新計(jì)算
            if(rheight == -1){
                TreeNode curr = root.right;
                rheight = 0;
                while(curr != null){
                    curr = curr.left;
                    rheight++;
                }
            }
            // 深度相同，說(shuō)明結(jié)束點(diǎn)在右邊
            if(lheight == rheight){
                // 如果是不是最后一個(gè)節(jié)點(diǎn)，累加這一層的節(jié)點(diǎn)
                if(lheight != 0){
                    res += 1 << lheight;
                } else {
                // 如果是最后一個(gè)節(jié)點(diǎn)，結(jié)束點(diǎn)在右邊意味著右節(jié)點(diǎn)是缺失的，返回res+1
                    return res + 1;
                }
                root = root.right;
                lheight = rheight - 1;
                rheight = -1;
            // 否則結(jié)束點(diǎn)在左邊
            } else {
                // 如果是不是最后一個(gè)節(jié)點(diǎn)，累加這一層的節(jié)點(diǎn)
                if(rheight != 0){
                    res += 1 << rheight;
                } else{
                // 如果是最后一個(gè)節(jié)點(diǎn)，返回res+2
                    return res + 2;
                }
                root = root.left;
                lheight = lheight - 1;
                rheight = -1;
            }
        }
        return res;
    }
}