ChunNote
0%

leetCode-222:Count Complete Tree Nodes

发表于 分类于

问题描述

给定一个完全二叉树，要求用时间复杂度低于 O(n) 的解法算出二叉树的节点数量。题目链接：**点我**

样例输入输出

输入：[1,2,3]

输出：3

解释：树结构如下

1

/ \

2 3

输入：[]

输出：0

问题解法

最容易想到的解法是遍历树节点，但是这样的时间复杂度是 O(n) 不满足要求。结合完全二叉树的特点，可以先找出树的高度，计算除最后一层外的树节点数量，然后对每个节点，按右节点向下查找，如果在最后一层有节点，则说明在这一层上此节点左边的节点均存在，此时直接计算节点数量加到结果上，如果最后一层没有节点，则返回开始的地方，将右节点作为根节点进行递归计算。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution
{
    private int high = 0;

    private int count = 0;

    public int countNodes(TreeNode root)
    {
        if (root == null)
        {
            return 0;
        }
        
        if (root.left == null && root.right == null)
        {
            return 1;
        }
        
        TreeNode p = root;
        while (p != null)
        {
            p = p.left;
            high++;
        }

        count = (int) (Math.pow(2, high - 1) - 1);

        countNodes(root, 1);

        return count;
    }

    private boolean countNodes(TreeNode root, int level)
    {
        if (level != high - 1)
        {
            boolean isEnd = countNodes(root.left, level + 1);
            if (isEnd)
            {
                return isEnd;
            }

            TreeNode p = root;
            int temp = level;
            while (temp != high - 1)
            {
                p = p.right;
                temp++;
            }

            if (p.right != null)
            {
                count += Math.pow(2, (high - level - 1));
                return false;
            }

            return countNodes(root.right, level + 1);
        }

        if (root.right != null)
        {
            count += 2;
            return false;
        }

        if (root.left != null)
        {
            count += 1;
            return true;
        }

        return true;
    }
}