222 Count Complete Tree Nodes

222. Count Complete Tree Nodes
1. Question
Given acompletebinary tree, count the number of nodes.
Definition of a complete binary tree fromWikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2hnodes inclusive at the last level h.
2. Implementation
(1) Method 1
思路: 对于每个node，找出最左边和最右边的高度，如果这两个高度相同，说明这个树是完美二叉树，其node的数目等于 2^height - 1。如果这两个高度不同，递归地检测它的左子树和右子树是否完美二叉树，是的话就可以直接用公式计算, node数目等于它这个node加上左子树的node和右子树的node
1
class Solution {
2
    public int countNodes(TreeNode root) {
3
        if (root == null) {
4
            return 0;
5
        }
6
​
7
        int leftMostHeight = getHeight(root, true);
8
        int rightMostHeight = getHeight(root, false);
9
​
10
        if (leftMostHeight == rightMostHeight) {
11
            return (1 << leftMostHeight) - 1;
12
        }
13
​
14
        return 1 + countNodes(root.left) + countNodes(root.right);
15
    }
16
​
17
    public int getHeight(TreeNode node, boolean isLeft) {
18
        int height = 0;
19
​
20
        while (node != null) {
21
            if (isLeft) {
22
                node = node.left;
23
            }
24
            else {
25
                node = node.right;
26
            }
27
            ++height;
28
        }
29
        return height;
30
    }
31
}
Copied!
(2) Method 2 二分法
思路：根据Complete tree的leaf node as far left as possible的特点，对一个节点的左子树和右子树，我们分别找出最左的深度。如两边最左深度相同，说明左子树是完美二叉树，可以直接用公式计算node个数，否则右边子树的高度肯定小于左边子树，而且右边子树根据complete的特点也必然是完美二叉树，用公式计算其node个个数。这样就可以达到二分的效果
1
class Solution {
2
    public int countNodes(TreeNode root) {
3
        if (root == null) {
4
            return 0;
5
        }
6
​
7
        int count = 1;
8
​
9
        int leftHeight = getLeftMostHeight(root.left);
10
        int rightHeight = getLeftMostHeight(root.right);
11
​
12
        if (leftHeight == rightHeight) {
13
            count += (1 << leftHeight) - 1;
14
            count += countNodes(root.right);
15
        }
16
        else {
17
            count += (1 << rightHeight) - 1;
18
            count += countNodes(root.left);
19
        }
20
        return count;
21
    }
22
​
23
    public int getLeftMostHeight(TreeNode node) {
24
        int height = 0;
25
        while (node != null) {
26
            node = node.left;
27
            ++height;
28
        }
29
        return height;
30
    }
31
}
Copied!
3. Time & Space Complexity
Method 1: 时间复杂度 O(h^2), 解析: 最坏的情况是每个子树都不是完美二叉树，所以对于每个node，都要花2h的时间去找出它的左子树和右子树的高度，总的时间为 2h + 2(h-1) + 2(h-2) +. ... + 2 => O(h^2), 空间复杂度O(h)
Method 2: 时间复杂度: O(h^2), 空间复杂度O(h)
4. References
​http://blog.csdn.net/jmspan/article/details/51056085​

623 Add One Row to Tree

450 Delete Node in a BST

Last modified 2yr ago

Copy link

Contents

222. Count Complete Tree Nodes

1. Question

2. Implementation

3. Time & Space Complexity

4. References