222. Count Complete Tree Nodes
给一个complete binary tree，计算这个树总共有几个节点
思路：
一开始的想法就是直接DFS去遍历整个树
计算出总共有几个节点
后来看了一下别人的解法
发现可以分别去计算左子树和右子树的高度
1.当左子树的高度=右子树:
这时候左子树一定是perfect binary tree
所以左子树的node数量=2^(左子树高度)-1
总node数量=1+2^(左子树高度)-1+countNodes(root->right)
2.当左子树高度!=右子树
这时候右子树一定是perfect binary tree
同理总node数量=1+2^(右子树高度)-1+countNodes(root->left)
C code :
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int countNodes(struct TreeNode* root) {
if (!root){
return 0;
}
int l=getdepth(root->left),r=getdepth(root->right);
if (r==l){
return (1<<l) +countNodes(root->right);
}else{
return (1<<r) +countNodes(root->left);
}
}
int getdepth(struct TreeNode* root){
if (!root){
return 0;
}
return 1+getdepth(root->left);
}
每日leetcode文 真的满好赚P币的
以后多发一点好了
不然废文都赚不到多少

大师

大师

大师 阿北DFS忘光光