题目大意

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 image.png

解题思路

方式一：中序遍历 升序

利用中序遍历 后，判断是否是升序即可，但凡有一个不是升序的直接就返回false

  1. class Solution {
  2.         TreeNode max;
  4.         public boolean isValidBST(TreeNode root) {
  5.             if (root == null) {
  6.                 return true;
  7.             }
  8.             //left
  9.             boolean left = isValidBST(root.left);
  10.             if (!left) {
  11.                 return false;
  12.             }
  13.             if (max != null && root.val <= max.val) {
  14.                 return false;
  15.             }
  16.             max = root;
  17.             //left
  18.             boolean right = isValidBST(root.right);
  20.             return right;
  22.         }

方式二：分治思想

  1. class Solution {
  3.         public boolean isValidBST(TreeNode root) {
  5.             if (root == null) {
  6.                 return true;
  7.             }
  8.             return helper(root, null, null);
  9.         }
  11.         /**
  12.          * 对于一个节点来说 先给他一个范围[min,max]
  13.          * 判断当前节点v是否在这个范围里面，如果不在直接就return false ，否则继续递归
  14.          * 递归操作时  左子树从 [min,v-1] ,对于右子树从[v+1,max]
  15.          */
  16.         private boolean helper(TreeNode root, Integer min, Integer max) {
  17.             if (root == null) {
  18.                 return true;
  19.             }
  20.             if ((max != null && root.val >= max) || (min != null && root.val <= min)) {
  21.                 return false;
  22.             }
  23.             //区间范围 [min,val]
  24.             boolean left = helper(root.left, min, root.val);
  25.             //[val,max]
  26.             boolean right = helper(root.right, root.val, max);
  27.             return left && right;x
  28.         }
  29.     }