题目描述（中等难度）

输入一个树，判断该树是否是合法二分查找树，95题做过生成二分查找树。二分查找树定义如下：

解法一

开始的时候以为可以很简单的用递归写出来。想法是，左子树是合法二分查找树，右子树是合法二分查找树，并且根节点大于左孩子，小于右孩子，那么当前树就是合法二分查找树。代码如下：

当然，这个解法没有通过。对于下面的解，结果利用上边的解法是错误的。

  2.     /  \
  3.    5   15
  4.       /  \
  5.      6   20

虽然满足左子树是合法二分查找树，右子树是合法二分查找树，并且根节点大于左孩子，小于右孩子，但这个树不是合法的二分查找树。因为右子树中的 6 小于当前根节点 10。所以我们不应该判断「根节点大于左孩子，小于右孩子」，而是判断「根节点大于左子树中最大的数，小于右子树中最小的数」。

  1. public boolean isValidBST(TreeNode root) {
  2.     if (root == null || root.left == null && root.right == null) {
  3.         return true;
  4.     }
  5.     //左子树是否合法
  6.     if (isValidBST(root.left)) {
  7.         if (root.left != null) {
  8.             int max = getMaxOfBST(root.left);//得到左子树中最大的数
  9.             if (root.val <= max) { //相等的情况，代表有重复的数字
  10.                 return false;
  11.             }
  12.         }
  14.     } else {
  15.         return false;
  16.     }
  18.     //右子树是否合法
  19.     if (isValidBST(root.right)) {
  20.         if (root.right != null) {
  21.             int min = getMinOfBST(root.right);//得到右子树中最小的数
  22.             if (root.val >= min) { //相等的情况，代表有重复的数字
  23.                 return false;
  24.             }
  25.         }
  27.     } else {
  28.         return false;
  29.     }
  30.     return true;
  31. }
  33. private int getMinOfBST(TreeNode root) {
  34.     int min = root.val;
  35.     while (root != null) {
  36.         if (root.val <= min) {
  37.             min = root.val;
  38.         root = root.left;
  39.     }
  40.     return min;
  41. }
  43. private int getMaxOfBST(TreeNode root) {
  45.     while (root != null) {
  46.         if (root.val >= max) {
  47.             max = root.val;
  48.         }
  49.         root = root.right;
  50.     }
  51.     return max;
  52. }

解法二

来利用另一种思路，参考。

解法一中，我们是判断根节点是否合法，找到了左子树中最大的数，右子树中最小的数。 由左子树和右子树决定当前根节点是否合法。

但如果正常的来讲，明明先有的根节点，按理说根节点是任何数都行，而不是由左子树和右子树限定。相反，根节点反而决定了左孩子和右孩子的合法取值范围。

可以观察到，左孩子的范围是 （父结点左边界，父节点的值），右孩子的范围是（父节点的值，父节点的右边界）。

还有个问题，java 里边没有提供负无穷和正无穷，用什么数来表示呢？

方案一，假设我们的题目的数值都是 Integer 范围的，那么我们用不在 Integer 范围的数字来表示负无穷和正无穷。用 long 去存储。

  1. public boolean isValidBST(TreeNode root) {
  2.     long maxValue = (long)Integer.MAX_VALUE + 1;
  3.     long minValue = (long)Integer.MIN_VALUE - 1;
  4.     return getAns(root, minValue, maxValue);
  5. }
  7. private boolean getAns(TreeNode node, long minVal, long maxVal) {
  8.     if (node == null) {
  9.         return true;
  10.     }
  11.     if (node.val <= minVal) {
  12.         return false;
  13.     }
  14.     if (node.val >= maxVal) {
  15.         return false;
  16.     }
  17.     return getAns(node.left, minVal, node.val) && getAns(node.right, node.val, maxVal);
  18. }

方案二：传入 Integer 对象，然后 null 表示负无穷和正无穷。然后利用 JAVA 的自动装箱拆箱，数值的比较可以直接用不等号。

  1. public boolean isValidBST(TreeNode root) {
  2.     return getAns(root, null, null);
  3. }
  5. private boolean getAns(TreeNode node, Integer minValue, Integer maxValue) { 
  6.     if (node == null) {
  7.         return true;
  8.     }
  9.     if (minValue != null && node.val <= minValue) {
  10.         return false;
  11.     }
  12.     if (maxValue != null && node.val >= maxValue) {
  13.         return false;
  14.     }
  15.     return getAns(node.left, minValue, node.val) && getAns(node.right, node.val, maxValue);
  16. }

解法三 DFS BFS

解法二其实就是树的 DFS，也就是二叉树的先序遍历，然后在遍历过程中，判断当前的值是是否在区间中。所以我们可以用栈来模拟递归过程。

上边的 DFS 可以看出来一个缺点，就是我们判断完当前元素后并没有出栈，后续还会回来得到右孩子后才会出栈。所以其实我们可以用 BFS，利用一个队列，一层一层的遍历，遍历完一个就删除一个。

  1. public boolean isValidBST(TreeNode root) {
  2.     if (root == null || root.left == null && root.right == null) {
  3.     }
  4.     //利用三个队列来保存对应的节点和区间
  5.     Queue<TreeNode> queue = new LinkedList<>();
  7.     Queue<Integer> maxValues = new LinkedList<>();
  8.     //头结点入队列
  9.     TreeNode pNode = root;
  10.     queue.offer(pNode);
  11.     minValues.offer(null);
  12.     maxValues.offer(null);
  13.     while (!queue.isEmpty()) {
  14.         //判断队列的头元素是否符合条件并且出队列
  15.         Integer minValue = minValues.poll();
  16.         Integer maxValue = maxValues.poll();
  17.         pNode = queue.poll();
  18.         if (minValue != null && pNode.val <= minValue) {
  19.             return false;
  20.         }
  21.         if (maxValue != null && pNode.val >= maxValue) {
  22.             return false;
  23.         }
  24.         //左孩子入队列
  25.         if(pNode.left!=null){
  26.             queue.offer(pNode.left);
  27.             minValues.offer(minValue);
  28.             maxValues.offer(pNode.val);
  29.         }
  30.         //右孩子入队列
  31.         if(pNode.right!=null){
  32.             queue.offer(pNode.right);
  33.             minValues.offer(pNode.val);
  34.             maxValues.offer(maxValue);
  35.         } 
  36.     }
  37.     return true;
  38. }

解法四 中序遍历

参考这里>)。

中序遍历顺序会是左孩子，根节点，右孩子。二分查找树的性质，左孩子小于根节点，根节点小于右孩子。

是的，如果我们将中序遍历的结果输出，那么将会到的一个从小到大排列的序列。

所以我们只需要进行一次中序遍历，将遍历结果保存，然后判断该数组是否是从小到大排列的即可。

更近一步，由于我们只需要临近的两个数的相对关系，所以我们只需要在遍历过程中，把当前遍历的结果和上一个结果比较即可。

  1. public boolean isValidBST(TreeNode root) {
  2.     if (root == null) return true;
  3.     Stack<TreeNode> stack = new Stack<>();
  4.     TreeNode pre = null;
  5.     while (root != null || !stack.isEmpty()) {
  6.         while (root != null) {
  7.             stack.push(root);
  8.             root = root.left;
  9.         }
  10.         root = stack.pop();
  11.         if(pre != null && root.val <= pre.val) return false;
  12.         pre = root;
  13.         root = root.right;
  14.     }
  15.     return true;

总

这几天都是二叉树的相关题，主要是对前序遍历，中序遍历的理解，以及 DFS，如果再用好递归，利用栈模拟递归，题目就很好解了。

添加好友一起进步~

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 查看详情