[LeetCode] Count Complete Tree Nodes
Count Complete Tree Nodes
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 2hnodes inclusive at the last level h.
解题思路：
题意为计算完全二叉树的节点数目。完全二叉树是指除了最底层的节点之外的节点都有两个孩子节点，且最底层的节点尽量靠左的二叉树。
解法1：暴力遍历法，用递归一个个遍历。这种方法的时间复杂度为O(N)，会产生超时错误。
/**
* 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) {
if(root==NULL){
return 0;
}
return 1 + countNodes(root->left) + countNodes(root->right);
}
};解法2：注意到对于一个完全二叉树来说，任何一个节点，以其左/右孩子为根节点的子树高度最多相差一，且最多只有一个子树不是满二叉树（除叶子节点外，所有节点都有两个子节点，且叶子节点在同一层）。计算某个节点ROOT的最左和最右高度LH、RH，若LH==RH，那么以该节点为根节点的子树节点数目为2^(LH)-1，否则节点数目=1+以ROOT->left为根节点的子树节点数目+以ROOT->right为根节点的子树节点数目
注意一个小技巧，2^n次方可以通过移位来获得。
该方法的时间复杂度为O(h^2)，因为最耗时的操作是计算以某个节点为根节点的树的高度，最差情况下扫描次数为（1+2+...+h）*2。
/**
* 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) {
if(root==NULL){
return 0;
}
int leftH = getLeftHeight(root);
int rightH = getRightHeight(root);
if(leftH == rightH){
return ( (1<<leftH) - 1);
}
return 1 + countNodes(root->left) + countNodes(root->right);
}
int getLeftHeight(TreeNode* root){
int h = 0;
while(root!=NULL){
h++;
root = root->left;
}
return h;
}
int getRightHeight(TreeNode* root){
int h = 0;
while(root!=NULL){
h++;
root = root->right;
}
return h;
}
};
0 条评论