摘要：根據這個特征，用二分法來將有序數組轉換為一顆二叉搜索樹。邊界條件向下取整得到中間值遞歸二分法接下來我們驗證下一棵樹是否滿足二叉搜索樹。二驗證二叉搜索樹相關題目驗證二叉搜索樹中等思路就是，中序遍歷如果滿足遞增的就行。

二叉樹大家都知道，二叉搜索樹滿足以下特征：

節點的左子樹只包含小于當前節點的數
節點的右子樹只包含大于當前節點的數
所有左子樹和右子樹自身必須也是二叉搜索樹

相關題目：leetcode 108.將有序數組轉換為二叉搜索樹 [中等]

那么如何將一個有序數組轉換為一顆二叉搜索樹？

二叉搜索樹的每一個分支的根節點都是他的中間值。根據這個特征，用二分法來將有序數組轉換為一顆二叉搜索樹。

const sortedArrayToBST = nums => {
    // 邊界條件
    if (nums.length === 0) {
        return null;
    } 
    if (nums.length === 1) {
        return new TreeNode(nums[0]);
    }
    // 向下取整得到中間值
    let mid = Math.floor(nums.length / 2);
    let root = new TreeNode(nums[mid]);
    // 遞歸 二分法
    root.left =  sortedArrayToBST(nums.slice(0, mid));
    root.right =  sortedArrayToBST(nums.slice(mid + 1));
    return root;
};

接下來我們驗證下一棵樹是否滿足二叉搜索樹。

相關題目：leetcode 98.驗證二叉搜索樹 [中等]

思路就是，中序遍歷如果滿足遞增的就行。

用一個max作為驗證值的變量，用中序遍歷前面的值和后面的值作比較，一直遞增則滿足二叉搜索樹。

const isValidBST = root => {
    let isValidBSTFlag = true;
    let max = -Number.MAX_VALUE;
    const orderSearch = root => {
        if (root) {
            orderSearch(root.left);
            if (root.val > max) {
                max = root.val;
            } else {
                isValidBSTFlag = false;
            }
            orderSearch(root.right);
        }
    }
    orderSearch(root);
    return isValidBSTFlag;
};

上一個非遞歸解法。

非遞歸中序遍歷的思路就是使用棧，將節點的左子樹壓入直到葉節點，然后操作完左子樹跟根節點后再操作右子樹。

循環反復，直到?？?。

const isValidBST = root => {
    if(!root) return true;
    let stack = [];
    let isValidBSTFlag = true;
    let max = -Number.MAX_VALUE;
    while (1) {
        while(root != null){
            stack.push(root);
            root = root.left;
        }
        if (stack.length === 0) break;
        let node = stack.pop();
        if (node.val > max) {
            max = node.val;
        } else {
            isValidBSTFlag = false;
            break;
        }
        root = node.right;
    }
    return isValidBSTFlag;
}

相關題目：leetcode 701.二叉搜索樹中的插入操作 [中等]

將值插入二叉搜索樹，只要樹在插入后仍保持為二叉搜索樹即可。

思路：找到大于插入節點值的節點，將要插入的節點作為該節點的左子樹。注意細節。

這里還是用中序遍歷，中序遍歷能很好地解決一種情況，就是要插入的節點值比樹中的所有節點還大。

這種情況，找到樹中最大值的節點，將插入的節點作為該節點的右節點。

沒用遞歸，方便理解。

const insertIntoBST = (root, val) => {
    let stack = [];
    let r = root;
    let node = null;
    while (1) {
        while(root != null) {
            stack.push(root);
            root = root.left;
        }
        if (stack.length === 0) break;
        node = stack.pop();
        // 找到大于插入節點值的節點
        if (node.val > val) {
            let newNode = new TreeNode(val);
            newNode.left = node.left;
            // 這里是細節
            node.left = newNode;
            break;
        }
        root = node.right;
    }
    // 要插入的節點值比樹中的所有節點還大
    if (val > node.val) {
        node.right = new TreeNode(val);
    }
    return r;
};

相關題目：leetcode 99.恢復二叉搜索樹 [困難]

要求：二叉搜索樹中的兩個節點被錯誤地交換。請在不改變其結構的情況下，恢復這棵樹。

思路：利用中序遍歷找到錯誤的兩個節點s1，s2。交換這兩個節點。

用一個數組保存遍歷的值，如果前一個節點大于后一個節點，則s1肯定是前一個節點，后一個節點不一定是s2，繼續遍歷尋找找到s2。

const recoverTree = root => {
    let res = [];
    let s1 = s2 = null;
    const orderSearch = root => {
        if (root) {
            orderSearch(root.left);
            if (res.length !== 0) {
                if (res[res.length - 1].val > root.val) {
                    // 第一個找到的才是s1
                    !s1 && (s1 = res[res.length - 1]);
                    // 若有第二次，第二次的才是s2
                    s2 = root;
                }
            }
            
            res.push(root)
            orderSearch(root.right);
        }
    }
    orderSearch(root);
    [s1.val, s2.val] = [s2.val, s1.val];
    return root;
};

二叉搜索樹跟排序相關，總是圍繞著中序遍歷進行操作。

遞歸代碼簡潔但是不好理解，非遞歸相對容易理解一些，兩者效率差不太大，看場景使用。