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忘光光