Algorithms & Data Structure : LeetCode 222. Count Complete Tree Nodes

題目：

Count Complete Tree Nodes - LeetCode

這個問題很好的演示了，該怎麼把一個問題拆解成多個步驟，並將一個個步驟好好地實做出來。

我的解法：

時間複雜度： O(N + E)
空間複雜度： O(1)
N 為節點個數， E 為邊的個數

這題如果只是單純解題的話，是個很簡單的一題，任何的 Tree Traversal 都可以解掉，但是題目的敘述有說，時間複雜度必須要低於 O(N)。

class Solution {
public:
    void dfs(TreeNode *root, int *res) {
        (*res) += 1;
        
        if(root->left) {
            dfs(root->left, res);
        }
        
        if(root->right) {
            dfs(root->right, res);
        }
        
    }
    
    int countNodes(TreeNode* root) {
        if(!root) {
            return 0;
        }
        
        int res = 0;
        dfs(root, &res);
        return res;
    }
};

看完提示的解法：

時間複雜度：O(d²) == O(log²N)
空間複雜度：O(1)
d 為樹的高度，N 為節點個數。

看題是的解法真的會覺得。。。我不看提示的話，真的能往這個方向想嗎？可能給我一個月的時間也想不到吧？

能靠自己想出這個解法的人，實在是太厲害了。

class Solution {
public:
    void dfs(TreeNode *root, int *height) {
        if(root->left) {
            (*height) += 1;
            dfs(root->left, height);
        }
    }
  
    // 在這裡也使用二分搜尋，尋找最後一層的 index 節點是否存在    
    bool exist(int index, TreeNode *root, int left, int right) {        
        if(left == right) {
            if(root) {
                return true;
            } else {
                return false;
            }
        }
                
        bool res = false;
        int mid = (left + right) / 2;
        if(index <= mid) {
            res |= exist(index, root->left, left, mid);
        } else {
            res |= exist(index, root->right, mid + 1, right);
        }
        
        return res;
    }
    
    int countNodes(TreeNode* root) {
        if(!root) {
            return 0;
        }
        // 先使用一個深度優先搜尋找出這棵樹的高度。
        // 這個深度優先搜尋不用真得找出所有的點，只需要知道樹的高度就好。        
        // ( 也就是不停地往左子節點走 )
        int height = 0;
        dfs(root, &height);
        
        if(height == 0) {
            return 1;
        }
        // complete binary tree 的最後一層，可能有 1 ~ 2^d 個節點
        // 使用二分搜尋來找最後一層的節點個數      
        int ori_left = 0;
        int ori_right = (1 << height) - 1;
        
        int left = ori_left;
        int right = ori_right;
        int mid = 0;
        int maxVal = INT_MIN;
        while(left <= right) {
            mid = (left + right) / 2;
            if(exist(mid, root, 0, ori_right)) {
                maxVal = max(maxVal, mid);
                left = mid + 1;
            } else {
                right = mid - 1;   
            }
        }       
                        
        return ((1 << height) - 1) + (maxVal + 1);
    }
};

看完解答的解法：

時間複雜度：O(d²) == O(log²N)
空間複雜度：O(1)
d 為樹的高度，N 為節點個數。

省略了 dfs 的遞迴，以及 exist 的遞迴。

class Solution {
public:
    void computeDepth(TreeNode *root, int *height) {
        while(root->left) {
            (*height) += 1;
            root = root->left;
        }
    }
    
    bool exist(int index, TreeNode *root, int height) {        
        int left = 0;
        int right = (1 << height) - 1;
        int mid = 0;
        for(int i = 0;i < height;i++) {
            mid = (left + right) / 2;            
            if(index <= mid) {
                root = root->left;
                right = mid;
            } else {
                root = root->right;
                left = mid + 1;
            }
        }
        
        return root != NULL;
    }
    
    int countNodes(TreeNode* root) {
        if(!root) {
            return 0;
        }
        
        int height = 0;
        computeDepth(root, &height);
        
        if(height == 0) {
            return 1;
        }
        
        int left = 0;
        int right = (1 << height) - 1;
        int mid = 0;
        int maxVal = INT_MIN;
        while(left <= right) {
            mid = (left + right) / 2;
            if(exist(mid, root, height)) {
                maxVal = max(maxVal, mid);
                left = mid + 1;
            } else {
                right = mid - 1;   
            }
        } 
        return ((1 << height) - 1) + (maxVal + 1);
    }
};