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

求问 leetcode 上的一道 BST 题。

  •  
  •   Godjack · 31 天前 · 1511 次点击
    这是一个创建于 31 天前的主题,其中的信息可能已经有所发展或是发生改变。

    我的代码如下

    /**
     * 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
        2
    xiang578   31 天前
    建议把题目发一下,不能都不知道是什么。
        3
    wallriding   31 天前
    至少写个题号吧
        4
    Godjack   31 天前
        5
    Godjack   31 天前
    @wallriding 不好意思,我 sb 了,题号是 530,
        6
    iEverX   31 天前
    区别就是 prev,你的代码里不是全局的,退栈之后就没了
        7
    Godjack   31 天前
    @iEverX 谢谢你的回复, 但是 pre 和 inOrder()都是在 getMinimumDifference()中,只要 getMinimumDifference()函数没结束,inOrder()退栈之后应该 pre 还在吧,而且我把 pre 和 res 定义为类的变量结果也不对...
        8
    iEverX   31 天前   ♥ 2
    @Godjack #7 不清楚你怎么改的。你现在的代码,是没有办法判断左子树的,只能判断右子树。给你个例子。
    14 2 # 1 13
        9
    ksedz   31 天前   ♥ 1
    是 prev 的问题,没有全局更新
    你的答案里遍历完一个子树,prev 的更新没有回传到上一层调用

    比如
    [10,5,null,1,8]
        10
    Godjack   30 天前
    @ksedz 懂了,谢谢你,指针没理解好。
        11
    Godjack   30 天前
    @iEverX 虽然当时没理解你的意思,但是还是谢谢你的回复,现在我已经懂了。
        12
    jc89898   30 天前
    @Godjack java 有指针?
        13
    Godjack   30 天前 via Android
    @jc89898 呃,我这么说不严谨。
        14
    stebest   30 天前
    LeetCode CN 版的里面有题解
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2636 人在线   最高记录 5043   ·   Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 22ms · UTC 11:54 · PVG 19:54 · LAX 04:54 · JFK 07:54
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1