LeetCode 222 Count Complete Tree Nodes

Tag: LeetCode 二分搜索 Posted on 2020-06-07 11:25:30 Edited on 2020-06-07 11:26:22 Views: 7

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)

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