我的代码如下
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int getMinimumDifference(TreeNode root) {
TreeNode res = new TreeNode(Integer.MAX_VALUE);
TreeNode pre = null;
inOrder(root, res, pre);
return res.val;
}
private void inOrder(TreeNode node, TreeNode k, TreeNode pre) {
if (node==null) return;
inOrder(node.left, k, pre);
if (pre!=null) k.val = Math.min(k.val, node.val-pre.val);
pre = node;
inOrder(node.right, k, pre);
}
}
讨论区网友的代码如下
class Solution {
// do a inorder traversal
// compare current val with previous val
// update answer
private Integer prev;
private int ans;
public int getMinimumDifference(TreeNode root) {
ans = Integer.MAX_VALUE;
inorder(root);
return ans;
}
private void inorder(TreeNode root) {
if (root == null) return;
inorder(root.left);
if (prev != null)
ans = Math.min(ans, root.val - prev);
prev = root.val;
inorder(root.right);
}
}
部分测试通不过,自己实在找不出错误了,希望大家能帮忙看看。感激不尽
1
springz 2019-05-26 16:50:22 +08:00
|
2
xiang578 2019-05-26 16:59:53 +08:00
建议把题目发一下,不能都不知道是什么。
|
3
wallriding 2019-05-26 17:01:58 +08:00
至少写个题号吧
|
4
Godjack OP @xiang578 不好意思,我 sb 了,题号是 530,地址是 https://leetcode.com/problems/minimum-absolute-difference-in-bst/description/
|
5
Godjack OP @wallriding 不好意思,我 sb 了,题号是 530,
|
6
iEverX 2019-05-26 18:27:02 +08:00
区别就是 prev,你的代码里不是全局的,退栈之后就没了
|
7
Godjack OP @iEverX 谢谢你的回复, 但是 pre 和 inOrder()都是在 getMinimumDifference()中,只要 getMinimumDifference()函数没结束,inOrder()退栈之后应该 pre 还在吧,而且我把 pre 和 res 定义为类的变量结果也不对...
|
8
iEverX 2019-05-26 19:22:08 +08:00 2
@Godjack #7 不清楚你怎么改的。你现在的代码,是没有办法判断左子树的,只能判断右子树。给你个例子。
14 2 # 1 13 |
9
ksedz 2019-05-26 19:30:45 +08:00 1
是 prev 的问题,没有全局更新
你的答案里遍历完一个子树,prev 的更新没有回传到上一层调用 比如 [10,5,null,1,8] |
14
stebest 2019-05-27 10:21:26 +08:00
LeetCode CN 版的里面有题解
|