成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專(zhuān)欄INFORMATION COLUMN

leetcode每日一題-563:二叉樹(shù)的坡度

isLishude / 3472人閱讀

摘要：每日一題二叉樹(shù)的坡度鏈接二叉樹(shù)的坡度題目分析簡(jiǎn)單的問(wèn)題。首先明確思路，我們需要遍歷每一個(gè)點(diǎn)，然后求出該點(diǎn)左右子樹(shù)的值的總和，然后做差，答案累計(jì)這個(gè)差值即可。

leetcode每日一題-563:二叉樹(shù)的坡度

鏈接

二叉樹(shù)的坡度


題目



分析

簡(jiǎn)單的dfs問(wèn)題。首先明確思路，我們需要遍歷每一個(gè)點(diǎn)，然后求出該點(diǎn)左右子樹(shù)的值的總和，然后做差，答案累計(jì)這個(gè)差值即可。那么問(wèn)題就轉(zhuǎn)化到求每個(gè)節(jié)點(diǎn)左右子樹(shù)值的綜合上面，同樣是一個(gè)dfs問(wèn)題，但是這個(gè)問(wèn)題有一個(gè)優(yōu)化，我們?cè)谥蟮拇a部分進(jìn)行詳細(xì)的分析。



代碼

C++

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    int res = 0;    int findTilt(TreeNode* root) {        // 首先對(duì)節(jié)點(diǎn)判空,如果是空,那么結(jié)果為0,直接返回即可.        if(root == nullptr) return res;        // 遍歷整個(gè)樹(shù)        dfs(root);        // 返回結(jié)果值        return res;    }    void dfs(TreeNode* root)    {        // 分別記錄左右子樹(shù)值的總和,初始值為0        int l = 0, r = 0;        // 如果存在左子樹(shù)就更新左子樹(shù)值的總和        if(root->left) l = sum(root->left);        // 如果存在右子樹(shù)就更新右子樹(shù)值的總和        if(root->right) r = sum(root->right);        // 答案記錄一下差值        res += abs(l - r);        // 如果存在左節(jié)點(diǎn)就計(jì)算左節(jié)點(diǎn)的坡度        if(root->left) dfs(root->left);        // 如果存在右節(jié)點(diǎn)就計(jì)算右節(jié)點(diǎn)的坡度        if(root->right) dfs(root->right);    }    int sum(TreeNode* root)     {        // 計(jì)算當(dāng)前節(jié)點(diǎn)值的總和        // 左子樹(shù)的值        int l = 0;        // 右子樹(shù)的值        int r = 0;        // 如果存在左子樹(shù)就更新左子樹(shù)的值(遞歸更新)        if(root->left) l = sum(root->left);        // 如果存在右子樹(shù)就更新右子樹(shù)的值(遞歸更新)        if(root->right) r = sum(root->right);        // 返回當(dāng)前節(jié)點(diǎn)值的總和        return root->val + l + r;    }};

C++

優(yōu)化

我們經(jīng)過(guò)簡(jiǎn)單的思考就可以發(fā)現(xiàn)，解法一實(shí)在是太繁瑣了，我們每遍歷一個(gè)點(diǎn)，就需要查詢(xún)以當(dāng)前結(jié)點(diǎn)為跟的整個(gè)樹(shù)，其中存在大量的重復(fù)，那么是否可以?xún)?yōu)化這個(gè)過(guò)程呢？我們仔細(xì)觀察，其實(shí)在計(jì)算差值的時(shí)候，我們也是遍歷了整個(gè)樹(shù)，那么我們可以可以邊更新邊遍歷，我們先計(jì)算底層的值，然后用底層的值來(lái)更新更高一層的值，顯然是可以的。

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {    int res = 0;public:    int findTilt(TreeNode* root) {       	// 如果根節(jié)點(diǎn)非空就遞歸遍歷樹(shù)        if(root) dfs(root);        // 返回結(jié)果        return res;    }    // 邊計(jì)算差值邊求當(dāng)前節(jié)點(diǎn)的總和,從底層開(kāi)始向上遍歷    int dfs(TreeNode* root)    {        // 如果是葉子,就返回當(dāng)前值        if(!root->left and !root->right) return root->val;        // 計(jì)算當(dāng)前當(dāng)前節(jié)點(diǎn)的左右子樹(shù)總和,默認(rèn)值為0        int l = 0, r = 0;        // 如果存在左子樹(shù)就更新l,此時(shí),先去計(jì)算底層的值,向下遞歸        if(root->left) l = dfs(root->left);        // 如果存在右子樹(shù)就更新r,此時(shí),先去計(jì)算底層的值,向下遞歸        if(root->right) r = dfs(root->right);        // 記錄下差值        res += abs(l - r);        // 返回當(dāng)前節(jié)點(diǎn)的值的總和        return l + r + root->val;    }};

Java

class Solution {    int ans = 0;    public int findTilt(TreeNode root) {        dfs(root);        return ans;    }    public int dfs(TreeNode node) {        if (node == null) {            return 0;        }        int sumLeft = dfs(node.left);        int sumRight = dfs(node.right);        ans += Math.abs(sumLeft - sumRight);        return sumLeft + sumRight + node.val;    }}作者：LeetCode-Solution

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/123947.html

相關(guān)文章

  • LeetCode 563 二叉樹(shù)的坡度[dfs] HERODING的LeetCode之路

    摘要：解題思路一道非常簡(jiǎn)單的題目，不能被繞進(jìn)去，首先要把題目讀明白，左右坡度差本質(zhì)上是左右子樹(shù)和之差，那么問(wèn)題就簡(jiǎn)單了，每次，返回的就是當(dāng)前所在子樹(shù)之和，更新坡度差的話就是當(dāng)前左右子樹(shù)之差，這兩個(gè)要分開(kāi)來(lái)計(jì)算，代碼如下 ...

    VincentFF 評(píng)論0 收藏0

  • 前端 | 每天一個(gè) LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...

    張漢慶 評(píng)論0 收藏0

  • leetcode每日一題-110:平衡二叉樹(shù)

    摘要：每日一題平衡二叉樹(shù)鏈接平衡二叉樹(shù)題目分析遍歷樹(shù)，然后每次判斷樹(shù)的左右兩個(gè)子樹(shù)的差值即可。 leetcode每日一題-110:平衡二叉樹(shù) 鏈接 平衡二叉樹(shù) 題目 ...

    不知名網(wǎng)友 評(píng)論0 收藏0

  • leetcode每日一題-559:N叉樹(shù)的最大深度

    摘要：每日一題叉樹(shù)的最大深度鏈接叉樹(shù)的最大深度題目分析簡(jiǎn)單的搜索題目。只需要從根節(jié)點(diǎn)開(kāi)始一下整個(gè)叉樹(shù)就可以得到答案了。主要是對(duì)要理解和掌握叉樹(shù)的遍歷。代碼作者作者 lee...

    caiyongji 評(píng)論0 收藏0

  • ＜LeetCode天梯＞Day031 驗(yàn)證二叉搜索樹(shù)（遞歸+中序遍歷） | 初級(jí)算法 | Pytho

    摘要：有效二叉搜索樹(shù)定義如下節(jié)點(diǎn)的左子樹(shù)只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。所有左子樹(shù)和右子樹(shù)自身必須也是二叉搜索樹(shù)。而我們二叉搜索樹(shù)保證了左子樹(shù)的節(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值，根節(jié)點(diǎn)的值均小于右子樹(shù)的值，因此中序遍歷以后得到的序列一定是升序序列。 ...

    Genng 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<