leetcode 222. Count Complete Tree Nodes [Medium]

davidlei included in leetcode

2021-10-27 208 words One minute

Contents

題目連結

題目敘述

給予一棵 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.