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

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

節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)
節(jié)點(diǎn)的右子樹只包含大于當(dāng)前節(jié)點(diǎn)的數(shù)
所有左子樹和右子樹自身必須也是二叉搜索樹

相關(guān)題目：leetcode 108.將有序數(shù)組轉(zhuǎn)換為二叉搜索樹 [中等]

那么如何將一個(gè)有序數(shù)組轉(zhuǎn)換為一顆二叉搜索樹？

二叉搜索樹的每一個(gè)分支的根節(jié)點(diǎn)都是他的中間值。根據(jù)這個(gè)特征，用二分法來將有序數(shù)組轉(zhuǎn)換為一顆二叉搜索樹。

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;
};

接下來我們驗(yàn)證下一棵樹是否滿足二叉搜索樹。

相關(guān)題目：leetcode 98.驗(yàn)證二叉搜索樹 [中等]

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

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

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;
};

上一個(gè)非遞歸解法。

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

循環(huán)反復(fù)，直到?？?。

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;
}

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

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

思路：找到大于插入節(jié)點(diǎn)值的節(jié)點(diǎn)，將要插入的節(jié)點(diǎn)作為該節(jié)點(diǎn)的左子樹。注意細(xì)節(jié)。

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

這種情況，找到樹中最大值的節(jié)點(diǎn)，將插入的節(jié)點(diǎn)作為該節(jié)點(diǎn)的右節(jié)點(diǎn)。

沒用遞歸，方便理解。

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();
        // 找到大于插入節(jié)點(diǎn)值的節(jié)點(diǎn)
        if (node.val > val) {
            let newNode = new TreeNode(val);
            newNode.left = node.left;
            // 這里是細(xì)節(jié)
            node.left = newNode;
            break;
        }
        root = node.right;
    }
    // 要插入的節(jié)點(diǎn)值比樹中的所有節(jié)點(diǎn)還大
    if (val > node.val) {
        node.right = new TreeNode(val);
    }
    return r;
};

相關(guān)題目：leetcode 99.恢復(fù)二叉搜索樹 [困難]

要求：二叉搜索樹中的兩個(gè)節(jié)點(diǎn)被錯(cuò)誤地交換。請(qǐng)?jiān)诓桓淖兤浣Y(jié)構(gòu)的情況下，恢復(fù)這棵樹。

思路：利用中序遍歷找到錯(cuò)誤的兩個(gè)節(jié)點(diǎn)s1，s2。交換這兩個(gè)節(jié)點(diǎn)。

用一個(gè)數(shù)組保存遍歷的值，如果前一個(gè)節(jié)點(diǎn)大于后一個(gè)節(jié)點(diǎn)，則s1肯定是前一個(gè)節(jié)點(diǎn)，后一個(gè)節(jié)點(diǎn)不一定是s2，繼續(xù)遍歷尋找找到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) {
                    // 第一個(gè)找到的才是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;
};

二叉搜索樹跟排序相關(guān)，總是圍繞著中序遍歷進(jìn)行操作。

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