Dowemo
0 0 0 0

Given the root node root of a complete binary tree, return the number of nodes of the tree tree. If the node number of the complete binary tree is n, then the time complexity is lower than o ( n ).

The root node of a given tree rootPlease return to the size of the tree.

Idea: the binary tree with depth h has up to 2. h1 nodes ( h> = 1 ). In other words, the number of nodes in the 2 h-1.

/*
struct TreeNode {
 int val;
 struct TreeNode *left;
 struct TreeNode *right;
 TreeNode(int x) :
 val(x), left(NULL), right(NULL) {
 }
};*/
class CountNodes {
public:
 int count(TreeNode* root) {
 int res=0;
 countTree(root,res);
 return res;
 }
 void countTree(TreeNode* root,int &res){
 int lh=0,rh=0;
 if(root==NULL) return;
 res++;
 if(root->left==NULL&&root->right==NULL) return;
 TreeNode *lroot=root->left;
 TreeNode *rroot=root->right;
 while(lroot){//从左子树头节点开始,走到最后一个节点 
 lh++;//左子树的深度 
 lroot=lroot->left;
 }
 while(rroot){//从右子树头节点开始,走到最后一个节点 
 rh++;//右子树的深度
 rroot=rroot->left;
 }
 if(lh==rh){//遍历到最后,如果lh==rh,说明左右子树深度相等 
 res+=pow(2,lh)-1;//pow(x,y)求x的y次方 左子树是满二叉树,求其结点个数
 countTree(root->right,res);
 }else{
 res+=pow(2,rh)-1;//子树是满二叉树,求其结点个数
 countTree(root->left,res);
 }
 }
};





Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs