Count Node In CBT

发表于 | 分类于

Count Node In CBT

题目描述：

给定一棵完全二叉树，要求返回这棵树中的节点的个数。

例子：

见LeetCode222.

解题思路：

如果按照普通遍历的方式，会TLE；所以我们在找某个节点的左右子树的个数的时候，先判断其左右节点的深度，如果一样，说明当前节点一棵完全二叉子树，直接可以得到节点数量；否则则继续递归调用计算节点个数。

代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int getleft(TreeNode* root){
        int res = 0;
        while(root){
            root = root->left;
            res++;
        }
        return res;
        //左侧深度
    }
    int getright(TreeNode* root){
        int res = 0;
        while(root){
            root = root->right;
            res++;
        }
        return res;
        //右侧深度
    }
    int countNodes(TreeNode* root) {
        if (!root) return 0;
        int l = getleft(root);
        int r = getright(root);
        
        if (l == r) {
            return pow(2, l) - 1;
        }
        else{
            return countNodes(root->left) + countNodes(root->right) + 1;
        }
    }
};