【LeetCode】46 验证二叉搜索树

题目

image-20200627165627570

image-20200627165641057

image-20200627165701349

解题思路:

LC官方解释的非常清楚,配有视频和动图

https://leetcode-cn.com/problems/validate-binary-search-tree/solution/yan-zheng-er-cha-sou-suo-shu-by-leetcode-solution/

个人喜欢用中序遍历

只要是二叉搜索树相关的题目 都可以用中序遍历

代码:

class Solution {
  public boolean isValidBST(TreeNode root) {
    Stack<TreeNode> stack = new Stack();
    double inorder = - Double.MAX_VALUE;

    while (!stack.isEmpty() || root != null) {
      while (root != null) {
        stack.push(root);
        root = root.left;
      }
      root = stack.pop();
      // 如果中序遍历得到的节点的值小于等于前一个 inorder,说明不是二叉搜索树
      if (root.val <= inorder) return false;
      inorder = root.val;
      root = root.right;
    }
    return true;
  }
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×