222.Count Complete Tree Nodes

其實我也就只是很簡單的遍歷一遍, 沒想到就AC而且還99% beat

class Solution {
  public:
    int countNodes_(TreeNode *root) {
        int count = 1;
        if (root->left) {
            count += countNodes_(root->left);
        }
        if (root->right) {
            count += countNodes_(root->right);
        }
        return count;
    }
    int countNodes(TreeNode *root) {
        if (root == nullptr) {
            return 0;
        }
int count = countNodes_(root);
        return count;
    }
};

但正確的方式應該還是要用到binary search, 首先我們先看全部的高有多少, 設為h, 然後我們先看右子樹的高是不是等於h-1

如果是 那我們可以把root移到右子樹的root, 然後count += 2^h -1

為什麼呢 因為右子樹的高度夠, 所以我們合理推斷左子樹的數量為2^h- 1, 是一個完全的二元樹, 全部是2^h -1 -1, 因為還要加上最上面的root

如果不是 那我們就是把root移到左子樹, 因為代表右子樹的最後一層都沒有東西, 然後數量就是2^h-2

這邊要注意的是, 當h == 1的時候, 如果只剩左子樹, 這樣h-2會出錯, 所以我們把它當作特別的case來判斷

class Solution {
  public:
    int getHeight(TreeNode *root) {
        if (!root) {
            return 0;
        } else {
            return getHeight(root->left) + 1;
        }
    }
    int countNodes(TreeNode *root) {
        if (!root) {
            return 0;
        }
        int res = 0;
        int h = getHeight(root);
while (root) {
            if (getHeight(root->right) == h -1) {
                res += 1 << (h - 1);
                root = root->right;
            } else {
                if (h == 1) {
                    res += 1;
                } else {
                    res += 1 << (h - 2);
                }
                root = root->left;
            }
            --h;
        }
        return res;
    }
};