LeetCode 222 Count Complete Tree Nodes

Tag: 二叉树 LeetCode Posted on 2022-02-08 00:32:47 Edited on 2022-02-08 00:51:27 Views: 171

概述

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

时间复杂度要求 O(n)

直接法

不管完全二叉树的条件,直接计数。

每个节点都调用一次函数,因此时间复杂度 O(n)。

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

利用完全二叉树的性质优化

https://labuladong.gitee.io/algo/2/18/32/

一棵完全二叉树的两棵子树,至少有一棵是满二叉树。

时间复杂度 O(logn * logn),因为函数本身是 logn(树的高度)。

每次函数调用时,两个子调用其中一个立刻返回,所以一共调用了树的高度次。

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (!root) return 0;
        int ld = 0;
        auto l = root;
        while (l) {
            l = l->left;
            ld ++;
        }
        int rd = 0;
        auto r = root;
        while (r) {
            r = r->right;
            rd ++;
        }
        
        if (ld == rd) { // full tree
            return int(pow(2, ld)) - 1;
        }
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
};

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