讨论/《初级算法》 - 验证二叉搜索树/
《初级算法》 - 验证二叉搜索树

二叉搜索树的中序遍历结果必然是递增数组或递减数组,因此中序遍历从头到尾判断是否满足递增或递减条件即可。

class Solution {
    List<Integer> list = new ArrayList<>();

    public boolean isValidBST(TreeNode root) {
        inOrderTraversal(root);
        for(int idx=1;idx<list.size();idx++){
            if(list.get(idx-1)>=list.get(idx)){
                return false;
            }
        }
        return true;
    }

    private void inOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrderTraversal(root.left);
        list.add(root.val);
        inOrderTraversal(root.right);
    }
}

分析一下:
实际上判断是否满足递增数组或递减数组时只需要前一个节点的值,因此可只保留前节点值即可。
中序遍历(参考大佬们的解法)

//前节点
    TreeNode preNode;
    //先序遍历
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        //左子树
        if (!isValidBST(root.left)) {
            return false;
        }
        //中间节点
        if (preNode != null && root.val <= preNode.val) {
            return false;
        }
        preNode = root;
        //右子树
        if (!isValidBST(root.right)) {
            return false;
        }
        return true;
    }

大佬们的最佳解答,给定范围的先序遍历:

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return false;
        }
        //判断左右子树是否满足范围
        return isValidBST(root.left, null, root.val) && isValidBST(root.right, root.val, null);
    }

    //先序遍历,当前节点不满足范围直接返回,否者判断左右子树是否满足搜索二叉树条件
    private boolean isValidBST(TreeNode node, Integer start, Integer end) {
        if (node == null) {
            return true;
        }
        //判断本节点
        if (start != null && node.val <= start) {
            return false;
        }
        if (end != null && node.val >= end) {
            return false;
        }
        //判断左右节点
        return isValidBST(node.left, start, node.val) && isValidBST(node.right, node.val, end);
    }
1
展开全部 21 讨论