首页 > 其他 > 详细

LeetCode Count Complete Tree Nodes

时间:2015-06-07 14:28:57      阅读:150      评论:0      收藏:0      [点我收藏+]

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
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 2h nodes inclusive at the last level h.

最简单的方法s1:

/**
 * 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 countNodes(TreeNode* root) {
        return count_nodes(root);
    }
    
    int count_nodes(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        int cnt = 1;
        cnt += count_nodes(root->left) + count_nodes(root->right);
        return cnt;
    }
};

当然TLE了

改进后s2:

因为完全二叉树如果去掉最后最后一层,那么剩下的这H-1层组成的树就是一颗满二叉树,不用去数其中的节点,直接可以计算得出为(2^(H-1))-1个,所以只要求出最后一层的节点个数加上即可。

 

LeetCode Count Complete Tree Nodes

原文:http://www.cnblogs.com/lailailai/p/4558393.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!