二叉搜索树怎么这么难做呢？

首先我们需要去了解一下, 二叉搜索树的性质:

1. 对于 BST的每一个节点 node，左子树节点的值都比 node的值要小,右子树的值都要比node的值大。
2. 对于BST的每一个节点node， 它的左侧和右侧都是 BST

这里需要说明一下的是,从刷算法的角度来讲,还有一个重要的性质: BST的中序遍历的结果是有序的(升序)。

那么我们开始吧, 最近一直拖更，很不好意思.

230. 二叉搜索树中第K个小的元素

思路梳理 如果这么理解, 产生一个升序的序列(数组)，那么我们可以根据第k个小的元素 1,2,3,4,5这里第1个小的元素在哪里？那不就是1嘛.刚好借助于BST中序遍历的结果。是不是就很巧了呢。

代码实现

/**

 * Definition for a binary tree node.

 * function TreeNode(val, left, right) {

 *     this.val = (val===undefined ? 0 : val)

 *     this.left = (left===undefined ? null : left)

 *     this.right = (right===undefined ? null : right)

 * }

 */

/**

 * @param {TreeNode} root

 * @param {number} k

 * @return {number}

 */

// BST 的两个性质 左边的比右边的大

// 中序遍历的结果是 升序的 


var kthSmallest = function(root, k) {

    // 返回结果 记录结果

    let res = 0;

    // 记录升序之后的排名

    let count = 0;

    function traverse(root, k) {

        // base case

        if (root === null) return


        traverse(root.left, k)

        //中序

        count++;

        if (count === k) {

           res = root.val;

           return res;

        }

        traverse(root.right, k)

    }


    //定义函数

    traverse(root, k)

    return res;

}

538. 把二叉搜索树转换为累加树

思路梳理

其实这道题需要需要一个反过来的想法, BST的中序遍历的结果是升序的, 如果我们稍微作为一下修改呢？

function traverse(root) {


    traverse(root.right)

    // 中序遍历的结果是不是就成了 逆序(降序)的方式排列呢

    // 这里做累加的结果

    traverse(root.left)

}

traverse(root)

通过逆向的思考方式, 我从 8开始，也就是右子树开始依次去右中左的方式去遍历和累加和，是不是会更好一点呢，你可以思考一下,仔细去看一下那颗实例树:

代码实现

/**

 * Definition for a binary tree node.

 * function TreeNode(val, left, right) {

 *     this.val = (val===undefined ? 0 : val)

 *     this.left = (left===undefined ? null : left)

 *     this.right = (right===undefined ? null : right)

 * }

 */

/**

 * @param {TreeNode} root

 * @return {TreeNode}

 */


 var convertBST = function(root) {

     // 升序变为降序

     // sum 记录累加和

     let sum = 0;


     function traverse(root) {

         // base case

         if (root === null) return


         traverse(root.right)

         // 维护累加值

         sum += root.val;

         root.val = sum;

         traverse(root.left)

     }

     traverse(root)

     return root;

 }

1038. 从搜索树到更大的和树

思路梳理

这道题和上题完全一样的思路和写法这里就不做赘述了

代码实现

/**

 * Definition for a binary tree node.

 * function TreeNode(val, left, right) {

 *     this.val = (val===undefined ? 0 : val)

 *     this.left = (left===undefined ? null : left)

 *     this.right = (right===undefined ? null : right)

 * }

 */

/**

 * @param {TreeNode} root

 * @return {TreeNode}

 */

var bstToGst = function(root) {

    // 升序变降序

    // 记录累加和

    let sum = 0;


    function traverse(root) {

        if (root === null) return;


        traverse(root.right)

        // 累加和

        sum += root.val;

        root.val = sum;

        traverse(root.left)

    }

    traverse(root)

    return root;

}

654. 最大二叉树

思路梳理

其实对于构建一颗二叉树最关键的是把root也就是把根节点找出来就好了。 那么我们就需要去遍历去找出数组中最大的值maxVal，把根节点root找出来了。 那么就可以把 maxVal左边和右边的数组进行递归，作为root的左右子树

// 伪代码

var constructMaximumBinaryTree = function([3,2,1,6,0,5]) {

    // 找出数组中的最大值

    let root = TreeNode(6)


    let root.left = constructMaximumBinaryTree([3,2,1])

    let root.right = constructMaximumBinaryTree([0,5])

    return root;

}

这里我们需要的注意的是如何去构建一个递归函数: 参数是如何要求的？ 因为需要 分离左子树和右子树 我们需要不断的确认子树的开始和结束的位置

function build (nums, start, end) {

    // base case

    if (left > right) return;


    let maxValue = -1, index = -1; // index 是最大值的索引值是重要的分离条件

    // find

    for (let i = start; i < end; i++) {

        if (nums[i] > maxValue) {

           maxValue = nums[i];

           index = i;

        }

    }

    // 此时去构建树 root;

    let root = new TreeNode(maxValue);


    root.left = build(nums, start, index - 1)

    root.right = build(nums, index + 1, end)

    // 别忘了返回 

    return root;

}

这里其实我们已经写出来的本题的核心代码了,需要我们自己耐心的组合一下就好了啊

代码实现

/**

 * Definition for a binary tree node.

 * function TreeNode(val, left, right) {

 *     this.val = (val===undefined ? 0 : val)

 *     this.left = (left===undefined ? null : left)

 *     this.right = (right===undefined ? null : right)

 * }

 */

/**

 * @param {number[]} nums

 * @return {TreeNode}

 */

var constructMaximumBinaryTree = function(nums) {

    let root = build(nums, 0, nums.length-1)

    return root;

}


function build(nums, start, end) {

     // base case 

     if (left > right) return;


     let maxVal = -1, index = -1;

     for (let i = start; i < end; i++) {

         if (nums[i] > maxVal) {

            maxVal = nums[i]

            index = i;

         }

     }


     // 制作树

     let root = new TreeNode(maxVal)


     root.left = build(nums, start, index - 1)

     root.right = build(nums, index + 1, end)

     return root;

}

98. 验证二叉搜索树

思路分析

BST类似的代码逻辑就是利用 左小右大的特性

function BST(root, target) {

    if (root.val === target) {

       // 找到目标做点什么呢

    }

    if (root.val < target) {

       // 右 比 root 大

       BST(root.right, target)

    }

    if (root.val > target) {

       // 左 比 root 小

       BST(root.left, target)

    }

}

那么对于我们去验证一棵树是不是合法的是需要注意一些事情的：

1. 对于每一个节点 root代码值都需要去检查它的左右孩子节点是否都是符合左小右大的原则
2. 从 BST的定义出发的话, root的整个左子树都要小于 root.val, 整个右子树都要大于 root.val

但是就会产生一个问题,就是对于某个节点,它只能管得了自己的左右子节点,如何去把约束关系传递给左右子树呢？

left.val < root.val < right.val

是不是可以借助于这种关系去约束他们呢？

主函数的定义

function isValidBST(root, null, null)

对于左子树来说 每一个左子树的 val 都需要满足于 min.val < val < root.val

isValidBST(root.left, min, root) 

那么同样的对于 每一个右子树的 val 都需要满足于 root.val < val < max.val

isValidBST(root.right, root, max)

代码实现

/**

 * Definition for a binary tree node.

 * function TreeNode(val, left, right) {

 *     this.val = (val===undefined ? 0 : val)

 *     this.left = (left===undefined ? null : left)

 *     this.right = (right===undefined ? null : right)

 * }

 */

/**

 * @param {TreeNode} root

 * @return {boolean}

 */

var isValidBST = function(root) {

    return isValid(root, null, null)

}


function isValid(root, min, max) {

    // 怎么就合法了呢？ 找完还一直没报false 不就是满足条件的吗

    if (root === null) return true;

    // 比最小的还小 不合法

    if (min !== null && root.val <= min.val) return false;

    // 比最大的还大。不合法

    if (max !== null && root.val >= max.val) return false;


    return isvalid(root.left, min, root) && isValid(root.right, root, max)

}

700. 二叉搜索树中的搜索

思路分析

其实，你看像不像我们上面提到的二叉树的思维模版呢？ 题目要求是 找到对应的val的节点, 并返回以该节点为根的子树 其实就是可以理解为 返回当前节点就好了 会带有以 该节点为根的一颗子树的。

代码实现

/**

 * Definition for a binary tree node.

 * function TreeNode(val, left, right) {

 *     this.val = (val===undefined ? 0 : val)

 *     this.left = (left===undefined ? null : left)

 *     this.right = (right===undefined ? null : right)

 * }

 */

/**

 * @param {TreeNode} root

 * @param {number} val

 * @return {TreeNode}

 */


 var searchBST = function(root, val) {

     // base case 

     if (root === null) return null;


     if (root.val === val) {

        return root;

     }


     if (root.val < val) {

       searchBST(root.right)

     }

     if (root.val > val) {

       searchBST(root.left)

     }


 }

701. 二叉搜索树中的插入操作

思路分析

这里 需要注意的一点就是你你怎么样才能插入呢？如果是 target === val说明不是空位置, 那就插不进去啊, 所以我们要插入的位置肯定是一个空位置, 你如果认真分析过 这个过程 你对 base case 有没有一个全新的认识呢？ 就是这里

代码实现

/**

 * Definition for a binary tree node.

 * function TreeNode(val, left, right) {

 *     this.val = (val===undefined ? 0 : val)

 *     this.left = (left===undefined ? null : left)

 *     this.right = (right===undefined ? null : right)

 * }

 */

/**

 * @param {TreeNode} root

 * @param {number} val

 * @return {TreeNode}

 */

var insertIntoBST = function(root, val) {

    // base case

    if (root === null) // 插入

    return new TreeNode(val)


    // if (root === val) 不需要了

    if (root.val < val) {

        insertIntoBST(root.right)

    }

    if (root.val > val) {

        insertIntoBST(root.left)

    }

}

450. 删除二叉搜索树中的节点

思路分析

先上一个基本的模版：

var deleteNode = function(root, key) {

    // 基本的摹本

    if (root === null) return null;


    if (root.val === key) {

       // 删除操作

    }


    if (root.val < key) {

       deleteNode(root.right, val)

    }

    if (root.val > key) {

       deleteNode(root.left, val)

    }

}

当 root.val === key的时候 需要我们去执行一个删除的逻辑了

case1: 没有子孩子

if (root.left === null && root.right) reture null;

case2: 只有一个非空节点的情况,那么需要这个非空的节点接替自己的位置

if (root.left === null) return root.right;

if (root.right === null) return root.left;

case3: 如果有两个节点就麻烦了,我们就需要把 左子树中最大的或者是右子树中最小的元素来接替自己， 我们采用第二种方式

if (root.left !== null && root.right !== null) {

    // 找到右子树中的最小的节点

    let minNode = getMin(root.right)

    // 把当前的值 替换为最小的值

    root.val = minNode;

    // 我们还需要把右子树中最小的值 删除掉

    root.right = deleteNode(root.right, minNode.val)

}

获取右子树中最小的元素

// 其实这里的最小的就是 左子树

function getMin(node) {

    while (node.left !== null)  继续找下面的左子树

    node = node.left;

    return node;  // 没有发现和前端的原型链好像啊

}

代码实现

/**

 * Definition for a binary tree node.

 * function TreeNode(val, left, right) {

 *     this.val = (val===undefined ? 0 : val)

 *     this.left = (left===undefined ? null : left)

 *     this.right = (right===undefined ? null : right)

 * }

 */

/**

 * @param {TreeNode} root

 * @param {number} key

 * @return {TreeNode}

 */

var deleteNode = function(root, key) {

    // 基本的摹本

    if (root === null) return null;


    if (root.val === key) {

       // 删除操作

       // case1, 2

       if (root.left === null) return root.right;

       if (root.right === null) return root.left;

       // case 3

       let minNode = getMin(root.right);

       root.val = minNode.val; // 一加

       root.right = deleteNode(root.right, minNode); // 一减

    }


    if (root.val < key) {

       deleteNode(root.right, val)

    }

    if (root.val > key) {

       deleteNode(root.left, val)

    }


    function getMin(node) {

        while(node.left !== null) node = node.left;

        return node;

    }

}