合法二叉搜索树

题目链接

合法二叉搜索树

题目描述

注意点

• 无

解答思路

• 第一个思路是将中序遍历，并将遍历到的节点的值存储到队列中，根据队列先进先出的特点将每次弹出的元素与其前面的值进行比较，如果队列是按照从小到大进行排序的，说明该树是合法二叉搜索树
• 第二个思路是递归，从根节点开始，每次传入相应子树的值所处的区间范围（根节点范围不限制），对于左子树，其下的节点值应该都小于根节点的值，对于右子树，其下的节点值应该都大于根节点的值…

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root, null, null);
    }

    public boolean helper(TreeNode root, Integer lower, Integer higher) {
        if (root == null) {
            return true;
        }
        if (lower != null && root.val <= lower) {
            return false;
        }
        if (higher != null && root.val >= higher) {
            return false;
        }
        return helper(root.left, lower, root.val) && helper(root.right, root.val, higher);
    }
}

关键点

• 递归的思想
• 在递归判断子树是否是合法二叉搜索树时，需要保证子树中的节点值始终处于(lower, higher)范围内，lower、higher可能为null，要注意空指针异常