摘要：每日一题二叉树的坡度链接二叉树的坡度题目分析简单的问题。首先明确思路，我们需要遍历每一个点，然后求出该点左右子树的值的总和，然后做差，答案累计这个差值即可。
简单的dfs问题。首先明确思路，我们需要遍历每一个点，然后求出该点左右子树的值的总和，然后做差，答案累计这个差值即可。那么问题就转化到求每个节点左右子树值的综合上面，同样是一个dfs问题，但是这个问题有一个优化，我们在之后的代码部分进行详细的分析。
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) { // 首先对节点判空,如果是空,那么结果为0,直接返回即可. if(root == nullptr) return res; // 遍历整个树 dfs(root); // 返回结果值 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); // 如果存在左节点就计算左节点的坡度 if(root->left) dfs(root->left); // 如果存在右节点就计算右节点的坡度 if(root->right) dfs(root->right); } int sum(TreeNode* root) { // 计算当前节点值的总和 // 左子树的值 int l = 0; // 右子树的值 int r = 0; // 如果存在左子树就更新左子树的值(递归更新) if(root->left) l = sum(root->left); // 如果存在右子树就更新右子树的值(递归更新) if(root->right) r = sum(root->right); // 返回当前节点值的总和 return root->val + l + r; }};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 { int res = 0;public: int findTilt(TreeNode* root) { // 如果根节点非空就递归遍历树 if(root) dfs(root); // 返回结果 return res; } // 边计算差值边求当前节点的总和,从底层开始向上遍历 int dfs(TreeNode* root) { // 如果是叶子,就返回当前值 if(!root->left and !root->right) return root->val; // 计算当前当前节点的左右子树总和,默认值为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); // 返回当前节点的值的总和 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文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/123947.html
摘要：解题思路一道非常简单的题目，不能被绕进去，首先要把题目读明白，左右坡度差本质上是左右子树和之差，那么问题就简单了，每次，返回的就是当前所在子树之和，更新坡度差的话就是当前左右子树之差，这两个要分开来计算，代码如下 ...
摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。 这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。 在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...
摘要：每日一题平衡二叉树链接平衡二叉树题目分析遍历树，然后每次判断树的左右两个子树的差值即可。 leetcode每日一题-110:平衡二叉树 链接 平衡二叉树 题目 ...
摘要：每日一题叉树的最大深度链接叉树的最大深度题目分析简单的搜索题目。只需要从根节点开始一下整个叉树就可以得到答案了。主要是对要理解和掌握叉树的遍历。代码作者作者 lee...
摘要：有效二叉搜索树定义如下节点的左子树只包含小于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。而我们二叉搜索树保证了左子树的节点的值均小于根节点的值，根节点的值均小于右子树的值，因此中序遍历以后得到的序列一定是升序序列。 ...
阅读 3158·2021-11-25 09:43
阅读 3283·2021-11-19 09:40
阅读 2230·2021-10-14 09:48
阅读 1074·2021-09-09 11:39
阅读 1730·2019-08-30 15:54
阅读 2691·2019-08-30 15:44
阅读 1875·2019-08-29 13:12
阅读 1418·2019-08-29 12:59
