leetcode 222. Count Complete Tree Nodes [Medium]

題目連結

題目敘述

給予一棵 Complete Binary Tree，求節點個數。

Complete Binary Tree 定義

BFS

最直觀的解法：用 BFS 走訪所有節點，每從 queue 取出一個節點就讓 count 加一。

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (!root) return 0;
        
        int cnt = 0;
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            TreeNode *node = q.front();
            q.pop();
            
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
            cnt++;
        }
        return cnt;
    }
};

Runtime: 24 ms, faster than 95.34% of C++ online submissions for Count Complete Tree Nodes.
Memory Usage: 31.5 MB, less than 6.88% of C++ online submissions for Count Complete Tree Nodes.

利用 Complete Binary Tree 的性質優化

Perfect Binary Tree 一定也是 Complete Binary Tree。讓 lnode 往左走、rnode 往右走，若最後 left height 與 right height 相同，代表這棵樹是 Perfect Binary Tree，節點數恰好是 $2^h - 1$（h 為樹高）；否則遞迴處理左右子樹。

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (!root) return 0;
        int lh = 0;
        int rh = 0;
        TreeNode *lnode = root, *rnode = root;
        
        while (lnode) {
            lnode = lnode->left;
            lh++;
        }
        
        while (rnode) {
            rnode = rnode->right;
            rh++;
        }
        
        if (lh == rh) return (1 << rh) - 1;
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

Runtime: 20 ms, faster than 99.27% of C++ online submissions for Count Complete Tree Nodes.
Memory Usage: 30.8 MB, less than 65.74% of C++ online submissions for Count Complete Tree Nodes.