Re: [閒聊] 每日LeetCode

[JIWP (神楽めあ的錢包)]

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
推 Che31128: 大師
推 DJYOSHITAKA: 大師
→ HGK: 大師 阿北DFS忘光光