【Check 51】2024-04-14 - 98. 验证二叉搜索树

[larscheng]

98. 验证二叉搜索树

[larscheng]

思路

• 递归：从根节点出发，每个节点都应该有自己的上下界，根节点的左子树应该处在(-n,root.val)，右子树应处在(root.val,n)

• 迭代：二叉搜索树的中序遍历为升序数组，通过迭代的方式进行中序遍历，同时判断迭代出的元素是否为升序

  代码

  
  class Solution1 {
      //递归判断每个节点的上下界
      public boolean isValidBST(TreeNode root) {
          return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
      }
  
      public boolean isValidBST(TreeNode node, long lower, long upper) {
          if (node == null) {
              return true;
          }
          if (node.val <= lower || node.val >= upper) {
              return false;
          }
          return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
      }
  }

```java

    //中序遍历升序数组
    //递归需要检查所有节点，迭代可以优化复杂度
    public boolean isValidBST(TreeNode root) {
        double lastNum = -Double.MAX_VALUE;
        Stack<TreeNode> stack = new Stack<>();

        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            TreeNode node = stack.pop();
            if (node.val<=lastNum){
                return false;
            }
            lastNum = node.val;

            root = node.right;
        }
        return true;
    }

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)