來源于公眾號數據結構和算法 ，作者山大王wld

問題描述

給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。

假設一個二叉搜索樹具有如下特征：

• 節(jié)點的左子樹只包含小于當前節(jié)點的數。

• 節(jié)點的右子樹只包含大于當前節(jié)點的數。

• 所有左子樹和右子樹自身必須也是二叉搜索樹。

示例 1:

輸入:

2

/ \

1 3

輸出: true

示例 2:

輸入:

5

/ \

1 4

 / \

3   6

輸出: false

解釋: 輸入為: [5,1,4,null,null,3,6]。

 根節(jié)點的值為 5 ，但是其右子節(jié)點值為 4 。

遞歸寫法

做這題之前我們首先要明白什么是二叉搜索樹，就是每個節(jié)點左子樹的值都比當前節(jié)點小，右子樹的值都比當前節(jié)點大。所以看到這里我們最先想到的就是遞歸，我最先想到的是下面這種寫法（注意是錯誤的）

1public boolean isValidBST(TreeNode root) {
2    if (root == null)
3        return true;
4    if (root.left != null && root.val <= root.left.val || root.right != null && root.val >= root.right.val)
5        return false;
6    return isValidBST(root.left) && isValidBST(root.right);
7}

如果一個結點是空的，我們默認他是有效的二叉搜索樹，否則如果左節(jié)點不為空，我們要判斷是否大于左節(jié)點的值，如果右節(jié)點不為空，我們還要判斷小于右節(jié)點的值，然后我們再以左右兩個子節(jié)點用相同的方式判斷?？雌饋砗孟駴]什么問題，但我們好像忽略了一個每個節(jié)點的上限和下限，比如下面這棵樹

image

注意6這個節(jié)點不光要小于15而且還要大于10，所以這里的每一個節(jié)點都是有一個范圍的，上面的代碼我只判斷了6比15小，但沒有和10進行比較，所以代碼是錯誤的。這里我們來給每個節(jié)點添加一個范圍，如果不在這個范圍之內直接返回false，比如6的范圍是(10,15)，很明顯他不在這個范圍內，所以他不是二叉搜索樹。根節(jié)點的范圍我們從Long.MIN_VALUE到Long.MAX_VALUE，來看下代碼

 1public boolean isValidBST(TreeNode root) {
 2    return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
 3}
 4
 5public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
 6    if (root == null)
 7        return true;
 8    //每個節(jié)點如果超過這個范圍，直接返回false
 9    if (root.val >= maxVal || root.val <= minVal)
10        return false;
11    //這里再分別以左右兩個子節(jié)點分別判斷，
12    //左子樹范圍的最小值是minVal，最大值是當前節(jié)點的值，也就是root的值，因為左子樹的值要比當前節(jié)點小
13    //右子數范圍的最大值是maxVal，最小值是當前節(jié)點的值，也就是root的值，因為右子樹的值要比當前節(jié)點大
14    return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
15}

中序遍歷遞歸

根據二叉搜索樹的性質我們知道，中序遍歷二叉搜索樹，遍歷的結果一定是有序的。中序遍歷時，判斷當前節(jié)點是否大于中序遍歷的前一個節(jié)點，也就是判斷是否有序，如果不大于直接返回 false。

 1//前一個結點，全局的
 2TreeNode prev;
 3
 4public boolean isValidBST(TreeNode root) {
 5    if (root == null)
 6        return true;
 7    //訪問左子樹
 8    if (!isValidBST(root.left))
 9        return false;
10    //訪問當前節(jié)點：如果當前節(jié)點小于等于中序遍歷的前一個節(jié)點直接返回false。
11    if (prev != null && prev.val >= root.val)
12        return false;
13    prev = root;
14    //訪問右子樹
15    if (!isValidBST(root.right))
16        return false;
17    return true;
18}

中序遍歷非遞歸

如果對樹的中序遍歷比較熟悉的話，這里面也有樹的中序遍歷的遞歸和非遞歸兩種寫法。我們完全可以把上面中序遍歷的遞歸改為非遞歸。

 1public boolean isValidBST(TreeNode root) {
 2    if (root == null)
 3        return true;
 4    Stack<TreeNode> stack = new Stack<>();
 5    TreeNode pre = null;
 6    while (root != null || !stack.isEmpty()) {
 7        while (root != null) {
 8            stack.push(root);
 9            root = root.left;
10        }
11        root = stack.pop();
12        if (pre != null && root.val <= pre.val)
13            return false;
14        //保存前一個訪問的結點
15        pre = root;
16        root = root.right;
17    }
18    return true;
19}

總結

這題可能最容易理解的是第一種解法，我們只需要給每個節(jié)點添加一個范圍，然后再分別遍歷每個節(jié)點，查看是否都在指定的范圍內，只要有一個不在范圍內，說明不是二叉搜索樹，直接返回false。后面兩種寫法是根據二叉搜索樹中序遍歷的特點來判斷，因為二叉搜索樹中序遍歷的結果是升序的，我們就按照二叉樹中序遍歷的方式來遍歷這棵二叉樹，然后在遍歷的時候順便保存一下前一個訪問的結點，判斷當前節(jié)點是否大于前一個結點的值，如果不大于直接返回false。