資訊專欄INFORMATION COLUMN
摘要：解題思路一道非常簡(jiǎn)單的題目，不能被繞進(jìn)去，首先要把題目讀明白，左右坡度差本質(zhì)上是左右子樹和之差，那么問題就簡(jiǎn)單了，每次，返回的就是當(dāng)前所在子樹之和，更新坡度差的話就是當(dāng)前左右子樹之差，這兩個(gè)要分開來計(jì)算，代碼如下
解題思路：
一道非常簡(jiǎn)單的題目，不能被繞進(jìn)去，首先要把題目讀明白，左右坡度差本質(zhì)上是左右子樹和之差，那么問題就簡(jiǎn)單了，每次dfs，返回的就是當(dāng)前root所在子樹之和，更新坡度差的話就是當(dāng)前root左右子樹之差，這兩個(gè)要分開來計(jì)算，代碼如下：
/** * 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 {private: int ans = 0;public: int findTilt(TreeNode* root) { dfs(root); return ans; } int dfs(TreeNode* root) { if(root == nullptr) { return 0; } int sumA = dfs(root -> left); int sumB = dfs(root -> right); ans += abs(sumA - sumB); return sumA + sumB + root -> val; }};文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/123942.html
摘要：每日一題二叉樹的坡度鏈接二叉樹的坡度題目分析簡(jiǎn)單的問題。首先明確思路，我們需要遍歷每一個(gè)點(diǎn)，然后求出該點(diǎn)左右子樹的值的總和，然后做差，答案累計(jì)這個(gè)差值即可。 lee...
摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
摘要：有效三角形的個(gè)數(shù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個(gè)數(shù)字?？偨Y(jié)本題和三數(shù)之和很像，都是三個(gè)數(shù)加和為某一個(gè)值。所以我們可以使用歸并排序來解決這個(gè)問題。注意因?yàn)闅w并排序需要遞歸，所以空間復(fù)雜度為 ...
題目地址：https://leetcode-cn.com/probl...題目描述： 給定一個(gè)非空二叉樹，返回其最大路徑和。 本題中，路徑被定義為一條從樹中任意節(jié)點(diǎn)出發(fā)，達(dá)到任意節(jié)點(diǎn)的序列。該路徑至少包含一個(gè)節(jié)點(diǎn)，且不一定經(jīng)過根節(jié)點(diǎn)。 示例 1: 輸入: [1,2,3] 1 / 2 3 輸出: 6 示例 2: 輸入: [-10,9,20,nul...
閱讀 782·2023-04-25 15:13
閱讀 1403·2021-11-22 12:03
閱讀 829·2021-11-19 09:40
閱讀 1913·2021-11-17 09:38
閱讀 1718·2021-11-08 13:18
閱讀 660·2021-09-02 15:15
閱讀 1774·2019-08-30 15:54
閱讀 2641·2019-08-30 11:12
