leetcode每日一題-563:二叉樹的坡度

isLishude 發(fā)布于2021-11-19 09:40 / 3463人閱讀

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

leetcode每日一題-563:二叉樹的坡度

鏈接

二叉樹的坡度

題目

分析

簡單的dfs問題。首先明確思路，我們需要遍歷每一個點，然后求出該點左右子樹的值的總和，然后做差，答案累計這個差值即可。那么問題就轉(zhuǎn)化到求每個節(jié)點左右子樹值的綜合上面，同樣是一個dfs問題，但是這個問題有一個優(yōu)化，我們在之后的代碼部分進行詳細的分析。

代碼

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) {        // 首先對節(jié)點判空,如果是空,那么結(jié)果為0,直接返回即可.        if(root == nullptr) return res;        // 遍歷整個樹        dfs(root);        // 返回結(jié)果值        return res;    }    void dfs(TreeNode* root)    {        // 分別記錄左右子樹值的總和,初始值為0        int l = 0, r = 0;        // 如果存在左子樹就更新左子樹值的總和        if(root->left) l = sum(root->left);        // 如果存在右子樹就更新右子樹值的總和        if(root->right) r = sum(root->right);        // 答案記錄一下差值        res += abs(l - r);        // 如果存在左節(jié)點就計算左節(jié)點的坡度        if(root->left) dfs(root->left);        // 如果存在右節(jié)點就計算右節(jié)點的坡度        if(root->right) dfs(root->right);    }    int sum(TreeNode* root)     {        // 計算當(dāng)前節(jié)點值的總和        // 左子樹的值        int l = 0;        // 右子樹的值        int r = 0;        // 如果存在左子樹就更新左子樹的值(遞歸更新)        if(root->left) l = sum(root->left);        // 如果存在右子樹就更新右子樹的值(遞歸更新)        if(root->right) r = sum(root->right);        // 返回當(dāng)前節(jié)點值的總和        return root->val + l + r;    }};

C++

優(yōu)化

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

/** * 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é)點非空就遞歸遍歷樹        if(root) dfs(root);        // 返回結(jié)果        return res;    }    // 邊計算差值邊求當(dāng)前節(jié)點的總和,從底層開始向上遍歷    int dfs(TreeNode* root)    {        // 如果是葉子,就返回當(dāng)前值        if(!root->left and !root->right) return root->val;        // 計算當(dāng)前當(dāng)前節(jié)點的左右子樹總和,默認值為0        int l = 0, r = 0;        // 如果存在左子樹就更新l,此時,先去計算底層的值,向下遞歸        if(root->left) l = dfs(root->left);        // 如果存在右子樹就更新r,此時,先去計算底層的值,向下遞歸        if(root->right) r = dfs(root->right);        // 記錄下差值        res += abs(l - r);        // 返回當(dāng)前節(jié)點的值的總和        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