• mersa
    2019-01-01
    老师这里视频是不是录制有问题啊。这节课视频老说之前强调了好多次中序遍历
     2
     16
  • 疯琴
    2018-11-26
    跟结点的右孩子已经比跟小了,不用看到3才发现问题。
    
     5
  • 这得从我捡到一个鼠标...
    2019-03-20
    建议不要只为了代码的简短而丢掉代码的可读性。

    public boolean isValidBST(TreeNode root) {
            if (root == null) {
                return true;
            }
            boolean left = isValidBST(root.left);
            boolean mid = pre >= root.val ? false : true;
            pre = root.val;
            boolean right = isValidBST(root.right);
            return left && mid && right;
        }
    展开

    作者回复: 这个代码的逻辑很清晰!!

     5
     4
  • 岳
    2018-10-29
    讲递归方法是,要注意覃老师讲的最小值不是子树上所有节点的最小值。
    比如以下,并非左子树最大值1小于3,且右子树最小值10大于3,它就是BST(这是错误的),不它并不是BST。
      3
      /\
    1 30
      /
      10
      \
      45

    这个解题思路还是要结合递归代码来理解。
    展开
    
     4
  • zixuan
    2018-10-28
    杆一下。解法②递归是直接按照定义来做,更容易理解;min/max是传入参数而不是讲思路时说的传出参数;解法①Threading反而是有一些经验才更容易想到。
    
     3
  • bywuu
    2019-05-01
    老师这个第三种方法怎么去使用啊?是不是还得先找出一个树的最大值和最小值,然后传进去?

    作者回复: 你说的没错,要从函数里层层传递进去。

    
     2
  • Trevor.赤
    2019-01-12
    func isValidBST(root *TreeNode) bool {
        r, _, _ := isVaildBST2(root)
        fmt.Print("yes")
        return r
    }
    func isVaildBST2(root *TreeNode) (bool, int, int) {
        var min, max, v int
        if root != nil {
            v = root.Val
        }
        if root.Left == nil {
            min = root.Val
        } else {
            lr, lmin, lmax := isVaildBST2(root.Left)
            if lr == false || lmax > v {
                return false, 0, 0
            }
            min = lmin
        }
        if root.Right == nil {
            max = root.Val
        } else {
            rr, rmin, rmax := isVaildBST2(root.Right)
            if rr == false || rmin < v {
                return false, 0, 0
            }
            max = rmax
        }
        return true, min, max
    }
    展开
    
     2
  • niubility
    2018-12-07
    使用老师的第一种方法(中序遍历后判断升序)实现.性能非常一般,还有很大优化空间.大家帮忙优化一下.
        public boolean isValidBST(TreeNode node) {
            if (node == null) {
                return true;
            }
            List<Integer> list = new ArrayList<>();
            InOrderTraverse(node, list);

            System.out.println(list);

            boolean result = true;

            for (int i = 0; i < list.size(); i++) {
                if (i < list.size() - 1 && list.get(i) >= list.get(i + 1)) {
                    result = false;
                    break;
                }

            }

            return result;
        }

        /**
         * 中序遍历
         *
         * @param node
         * @param list
         */
        public void InOrderTraverse(TreeNode node, List<Integer> list) {
            if (node == null) return;
            InOrderTraverse(node.left, list);
            list.add(node.val);
            InOrderTraverse(node.right, list);
        }
    展开
    
     1
  • Terry
    2018-11-03
    递归方法可以在最外层调用时把min和max分别设成-inf和inf,然后在递归的函数中不用再去判min或max是否为空。
    
     1
  • 胖胖虎
    2020-01-31
    5比1和4都来得大,从根节点开始,就不是二叉排序树了。
    
    
  • 神三元
    2020-01-25
    其实写出更加精简且可读性好的代码:

    var isValidBST = function(root) {
        let help = (node, min, max) =>{
            if(node == null) return true;
            if(node.val >= max || node.val <= min)
                return false;
            return help(node.left, min, Math.min(node.val, max))
                    && help(node.right, Math.max(node.val, min), max);
        }
        return help(root, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER);
    };
    展开
    
    
  • 世默
    2019-11-22
    面快手答的挺好,但最后这道题没作对,结果挂了 哎 早看到视频就好了
    
    
  • 又双叒叕是一年啊
    2019-11-04
    递归传入的 min max 分别是 二叉搜索树的 节点值 的 最小 最大值?

    作者回复: 当前子树里所有结点的值的上下界。

    
    
  • 关
    2019-08-12
    第二遍做这套题目了,有的东西要深入理解真的很难得感觉
     1
    
  • LeonTung
    2019-08-06
    如果return inorder == list(sorted(set(inorder))) 这样写,这道题的时间复杂度不再是O(n),而是O(nlogn)了
    
    
  • 傻傻木头人
    2019-07-15
    提供另外一种解法,利用迭代的方式中序遍历,记录上一次遍历到的结点,如果上一次遍历的结点的值大于等于当前的结点值,说明不是二叉搜索树。
    时间复杂度:O(n)
    空间复杂度:O(n)

    cpp实现

    bool isValidBST(TreeNode* root) {
        stack<TreeNode *> __stack;
        TreeNode *pre = nullptr;
        // 迭代的方式中序遍历
        while(root || !__stack.empty()) {
            while (root) {
                __stack.push(root);
                root = root->left;
            }
            root = __stack.top();
            __stack.pop();
            if (pre && pre->val >= root->val) {
                return false;
            }
            pre = root;
            root = root->right;
        }
        return true;
    }
    展开
    
    
  • 坤
    2019-07-10
    覃老师您好,请问LeetCode的golang的支持是不是不太好还是我的Golang不够好,对于同一个testcase,执行阶段没有问题,但是提交后的运行结果竟然是不一样的。代码如下:

    /**
     * Definition for a binary tree node.
     * type TreeNode struct {
     * Val int
     * Left *TreeNode
     * Right *TreeNode
     * }
     */

    var arr = make([]int, 0)

    func inOrder(root *TreeNode) {
        if root.Left != nil {
            inOrder(root.Left)
        }
        arr = append(arr, root.Val)
        if root.Right != nil {
            inOrder(root.Right)
        }
        
        
    }

    func isValidBST(root *TreeNode) bool {
        
        if root == nil {
            return true
        }
        if root.Left != nil {
            if root.Left.Val == -1 && root.Val == 0 {
                return true
            }
        }
        if root.Right != nil {
            if root.Right.Val == 1 && root.Val == 0 {
                return true
            }
        }
        if root.Left == nil && root.Right == nil {
            return true
        }
        inOrder(root)
        
        
        
        // fmt.Println(arr)
        for index,val := range arr {
            if index < len(arr) - 1 {
                // fmt.Println(index, val)
                if val >= arr[index+1] {
                    return false
                }
            }
            
        }
        return true
        
        
        
    }
    展开
    
    
  • 克里斯
    2019-06-21
    能不能讲二叉树递归的过程啊?二叉排序书都懂,然后这又不是玄学,为啥只可意会不可言传呢?
    
    
  • 克里斯
    2019-06-21
    每次用递归,心里都比较虚。
    前继结点为啥这样就能得到?
    
    
  • bywuu
    2019-04-30
    老师你的一开始的白板画错了吧?
    应该是:3
                1 5
                           2
    这个不应该是true啊?那么就是给的例子不太对,应该是[3,1,5,null,2]才是白板上的那个情况吧?
    
    
我们在线,来聊聊吧