LeetCode 222 Count Complete Tree Nodes

https://leetcode.com/problems/count-complete-tree-nodes/

当做普通二叉树进行处理

最简单的暴力方法，无视完全二叉树的条件，直接当做普通二叉树进行处理。

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

因为对于每个节点我们都遍历了一遍，复杂度为 O(N)

考虑到完全二叉树至少有一个子树是满二叉树

class Solution {
public:
    int countNodes(TreeNode* root) {
        TreeNode *left = root, *right = root;
        int leftHeight = 0, rightHeight = 0;
        while(left!=nullptr) {
            ++leftHeight; // Notice this is not left subtree's height
            left = left->left;
        }
        while(right!=nullptr) {
            ++rightHeight;
            right = right->right;
        }
        if(leftHeight == rightHeight) { // It's a perfect binary tree.
            return pow(2, leftHeight) - 1;
        } else {
            return countNodes(root->left) + countNodes(root->right) + 1;
        }
    }
};

while 循环的复杂度为树的高度即 O(log n)

然后递归了多少次呢？实际上由于其中一个子树为满二叉树，处理该子树时递归不再继续下去， 也就是说在树的每一层，我们最多只选择其中一个分支递归下去，则递归了树的高度即 log n 次， 则复杂度为 O(logN*logN)

Links: LeetCode-222-Count-Complete-Tree-Nodes

未经允许，禁止转载，本文源站链接：https://iamazing.cn/