LeetCode算法题-Binary Tree Tilt（Java实现）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode算法题-Binary Tree Tilt（Java实现），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2802字，纯文字阅读大概需要5分钟。
内容图文
这是悦乐书的第263次更新，第276篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第130题（顺位题号是563）。给定二叉树，返回整棵树的倾斜度。树节点的倾斜被定义为所有左子树节点值的总和与所有右子树节点值的总和之间的绝对差。 空节点倾斜0。整棵树的倾斜度定义为所有节点倾斜的总和。例如：
输入：
1
/ 2 3输出：1
说明：节点2的倾斜度为0，节点3的倾斜度为0，节点1的倾斜：| 2-3 | = 1，二叉树的倾斜：0 + 0 + 1 = 1。
注意：
任何子树中的节点值总和不会超过32位整数的范围。
所有倾斜值都不会超过32位整数的范围。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
根据题目对于倾斜度的定义，当前节点的左子树所有节点值之和与右子树所有节点值之和的绝对值就是倾斜度。我们先来看两个例子：
1
/ 2 3
/ \ / 4 5 6 7上面的二叉树自上而下可以计算的子树有三次，一是从根节点1开始，二是从左子树节点2开始，三是从右子树节点3开始。
|(2+4+5)-(3+6+7)| = 5
|4-5| = 1
|6-7| = 1
所以该二叉树的倾斜度是7。
1
/ 2 3
/ \
4 5上面的二叉树自上而下可以计算的子树有两次，一是从根节点1开始，二是从左子树节点2开始。
|(2+4+5)-3| = 8
|4-5| = 1
所以该二叉树的倾斜度是9。
如果从上往下计算，会出现重复计算，所以我们可以从下往上开始计算，使用递归的方法，先计算相邻左右节点的绝对值，然后返回到上一层父节点，附带加上父节点的节点值，相当于计算了其所在子树的节点值之和。
private int tilt = 0;
public int findTilt(TreeNode root) {
getNodeValue(root);
return tilt;
}
public int getNodeValue(TreeNode root) {
if (root == null) {
return 0;
}
int left = getNodeValue(root.left);
int right = getNodeValue(root.right);
tilt += Math.abs(left-right);
return left+right+root.val;
}03 第二种解法
还可以使用迭代的方法，依旧是从下往上开始计算，使用栈来实现，借助其先进后出的特性，在最后计算根节点的左右子树。中间还使用了HashMap，以节点为key，所在子树累加的节点值为value。
public int findTilt2(TreeNode root) {
if (root == null) {
return 0;
}
int sum = 0;
Stack<TreeNode> stack = new Stack<TreeNode>();
Map<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.peek();
if ((node.left == null || map.containsKey(node.left)) &&
(node.right == null || map.containsKey(node.right))) {
stack.pop();
int left = map.containsKey(node.left) ? map.get(node.left) : 0;
int right = map.containsKey(node.right) ? map.get(node.right) : 0;
sum += Math.abs(left - right);
map.put(node, left + right + node.val);
} else {
if (node.left != null && !map.containsKey(node.left)) {
stack.push(node.left);
}
if (node.right != null && !map.containsKey(node.right)) {
stack.push(node.right);
}
}
}
return sum;
}04 小结
算法专题目前已日更超过三个月，算法题文章130+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
内容总结
以上是互联网集市为您收集整理的LeetCode算法题-Binary Tree Tilt（Java实现）全部内容，希望文章能够帮你解决LeetCode算法题-Binary Tree Tilt（Java实现）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。