Re: [閒聊] 每日LeetCode已回收
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幣的
以後多發一點好了
不然廢文都賺不到多少
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.82.92.238 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1708149726.A.EBE.html
推
02/17 14:02,
1年前
, 1F
02/17 14:02, 1F
推
02/17 14:04,
1年前
, 2F
02/17 14:04, 2F
→
02/17 14:24,
1年前
, 3F
02/17 14:24, 3F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 687 之 719 篇)：