V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Godjack
V2EX  ›  Java

求问 leetcode 上的一道 BST 题。

  •  
  •   Godjack · 2019-05-26 16:37:01 +08:00 · 2230 次点击
    这是一个创建于 919 天前的主题,其中的信息可能已经有所发展或是发生改变。

    我的代码如下

    /**
     * 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);
        }
    }
    

    部分测试通不过,自己实在找不出错误了,希望大家能帮忙看看。感激不尽

    14 条回复    2019-05-27 10:21:26 +08:00
    xiang578
        2
    xiang578   2019-05-26 16:59:53 +08:00
    建议把题目发一下,不能都不知道是什么。
    wallriding
        3
    wallriding   2019-05-26 17:01:58 +08:00
    至少写个题号吧
    Godjack
        4
    Godjack   2019-05-26 17:32:18 +08:00
    Godjack
        5
    Godjack   2019-05-26 17:32:41 +08:00
    @wallriding 不好意思,我 sb 了,题号是 530,
    iEverX
        6
    iEverX   2019-05-26 18:27:02 +08:00
    区别就是 prev,你的代码里不是全局的,退栈之后就没了
    Godjack
        7
    Godjack   2019-05-26 19:00:42 +08:00
    @iEverX 谢谢你的回复, 但是 pre 和 inOrder()都是在 getMinimumDifference()中,只要 getMinimumDifference()函数没结束,inOrder()退栈之后应该 pre 还在吧,而且我把 pre 和 res 定义为类的变量结果也不对...
    iEverX
        8
    iEverX   2019-05-26 19:22:08 +08:00   ❤️ 2
    @Godjack #7 不清楚你怎么改的。你现在的代码,是没有办法判断左子树的,只能判断右子树。给你个例子。
    14 2 # 1 13
    ksedz
        9
    ksedz   2019-05-26 19:30:45 +08:00   ❤️ 1
    是 prev 的问题,没有全局更新
    你的答案里遍历完一个子树,prev 的更新没有回传到上一层调用

    比如
    [10,5,null,1,8]
    Godjack
        10
    Godjack   2019-05-26 21:26:15 +08:00
    @ksedz 懂了,谢谢你,指针没理解好。
    Godjack
        11
    Godjack   2019-05-26 21:27:48 +08:00
    @iEverX 虽然当时没理解你的意思,但是还是谢谢你的回复,现在我已经懂了。
    jc89898
        12
    jc89898   2019-05-26 22:26:18 +08:00
    @Godjack java 有指针?
    Godjack
        13
    Godjack   2019-05-27 07:40:57 +08:00 via Android
    @jc89898 呃,我这么说不严谨。
    stebest
        14
    stebest   2019-05-27 10:21:26 +08:00
    LeetCode CN 版的里面有题解
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3789 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 06:52 · PVG 14:52 · LAX 22:52 · JFK 01:52
    ♥ Do have faith in what you're doing.