这是悦乐书的第 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 + 篇, 公众号对话框回复 [数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/4d50ef575cae