面试题 04.05. 合法二叉搜索树

题目

实现一个函数，检查一棵二叉树是否为二叉搜索树。

示例1:

输入:

graph TB
2((2)) --- 1((1))
2 --- 3((3))

输出: true

示例2:

输入:

graph TB
5((5)) --- 1((1))
5 --- 4((4))
4 --- 3((3))
4 --- 6((6))

输出: false

解释: 输入为: [5,1,4,null,null,3,6]。根节点的值为 5 ，但是其右子节点值为 4 。

题解

public boolean isValidBST(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    // 中序遍历树
    Consumer<TreeNode> inorderTraversal = new Consumer<TreeNode>() {
        @Override
        public void accept(TreeNode node) {
            if (node == null) {
                return;
            }
            this.accept(node.left);
            list.add(node.val);
            this.accept(node.right);
        }
    };
    inorderTraversal.accept(root);

    // 若中序遍历结果是升序的 则是二叉搜索树 否则不是
    for (int i = 1, length = list.size(); i < length; i++) {
        if (list.get(i - 1) >= list.get(i)) {
            return false;
        }
    }

    return true;
}