十四 算法-二叉树

二叉树

定义

  // 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)
}

1. 二叉树的前/中/后序遍历

递归法

这里帮助大家确定下来递归算法的三个要素。每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！

确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

144 前序遍历

给你二叉树的根节点 root ，返回它节点值的前序遍历。

// 方法 一
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    let result=[]
    dfs(root,result)
    return result
};
const dfs=(root,result)=>{
    if(!root){
        return
    }
    result.push(root.val) // 只需要调整它的位置 就能确定是前中后序遍历
    dfs(root.left,result)
    dfs(root.right,result)
}
// 方法 二
/**
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function(root) {
    let res=Infinity
    let pre=null
    const traversal=(cur)=>{
        // 确定终止条件
        if(!cur) return
        // 确定单层递归逻辑
        traversal(cur.left)
        if(pre){
            res=Math.min(res,cur.val-pre.val) // 中序遍历时 进行逻辑处理
        }
        pre=cur
        traversal(cur.right)
    }
    traversal(root)
    return res
};

94 中序遍历

145 后序遍历

迭代法

为什么可以用迭代法（非递归的方式）来实现二叉树的前后中序遍历呢？

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

此时大家应该知道我们用栈也可以是实现二叉树的前后中序遍历了。

我们先看一下前序遍历。

前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。

为什么要先加入右孩子，再加入左孩子呢？因为这样出栈的时候才是中左右的顺序。

再来看后序遍历，先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序。

中序遍历

那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。

那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

// 先序迭代
var preorderTraversal = function(root) {
    if(!root){
        return []
    }
    // 迭代法
    let stack=[]
    let result=[]
    stack.push(root)
    while(stack.length){
        let temp=stack.pop()
        result.push(temp.val)
        temp.right && stack.push(temp.right)
        temp.left && stack.push(temp.left)
    }
    return result
}
// 后序迭代
var postorderTraversal = function(root) {
    const nums = [], stack = []
    if (!root) return nums
    stack.push(root)
    while (stack.length) {
        const cur = stack.pop()
        // 向前添加元素，构造反向顺序
        nums.unshift(cur.val)
        // 与先序的左右顺序相反
        if (cur.left) stack.push(cur.left)
        if (cur.right) stack.push(cur.right)
    }
    return nums
}
// 中序迭代 比较难理解
var inorderTraversal = function(root) {
    if(!root){
        return []
    }
    const res = [];
    const stk = [];
    while (root || stk.length) {
        while (root) {
            stk.push(root);
            root = root.left;
        }
        root = stk.pop();
        res.push(root.val);
        root = root.right;
    }
    return res;
}

2. 二叉树的层序遍历

102

bfs广度优先遍历

队列先进先出，符合一层一层遍历的逻辑

/ 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
// 输入：root = [3,9,20,null,null,15,7]
// 输出：[[3],[9,20],[15,7]]
var levelOrder = function(root) {
    //二叉树的层序遍历
    let queue=[]
    let res=[]
    if(!root){
        return res
    }
    queue.push(root)
    while(queue.length){
        let length=queue.length // 记录当前层级节点数
        let curNode=[]
        while(length--){
            let node=queue.shift()
            curNode.push(node.val) //存放每一层的节点 
            node.left && queue.push(node.left)  // 存放当前层下一层的节点
            node.right && queue.push(node.right)
        }
        res.push(curNode) //把每一层的结果放到结果数组
    }
    return res
};

3. 翻转二叉树

226 简单难理解

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

解析:这是一道很经典的二叉树问题。显然，我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 root\textit{root}root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root\textit{root}root 为根节点的整棵子树的翻转

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    if(!root) return null
    const right=invertTree(root.right)
    const left=invertTree(root.left)
    root.left=right
    root.right=left
    return root
};

4. 对称二叉树

101

给你一个二叉树的根节点 root ，检查它是否轴对称。

本题遍历只能是“后序遍历”，因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。

正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。

但都可以理解算是后序遍历，尽管已经不是严格上在一个树上进行遍历的后序遍历了。

其实后序也可以理解为是一种回溯，当然这是题外话，讲回溯的时候会重点讲的。

递归三部曲

确定递归函数的参数和返回值

因为我们要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是

个树，参数自然也是左子树节点和右子树节点。

返回值自然是bool类型。

确定终止条件

要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚！否则后面比较数值的时候就会操作空指针了。

节点为空的情况有：（注意我们比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点）

左节点为空，右节点不为空，不对称，return false
左不为空，右为空，不对称 return false
左右都为空，对称，返回true
此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：

左右都不为空，比较节点数值，不相同就return false

确定单层递归的逻辑

此时才进入单层递归的逻辑，单层递归的逻辑就是处理左右节点都不为空，且数值相同的情况。

比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
比较内测是否对称，传入左节点的右孩子，右节点的左孩子。
如果左右都对称就返回true ，有一侧不对称就返回false 。

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    //使用递归遍历左右子树 递归三部曲
    if(root===null){
        return true;
    }
    return compareNode(root.left,root.right);

};
 
    // 1. 确定递归的参数 root.left root.right和返回值true false 
    const compareNode=function(left,right){
        //2. 确定终止条件 空的情况
        if(left!==null&&right===null||left===null&&right!==null){
            return false
        }else if(left===null&&right===null){
            return true
        }else if(left.val!==right.val){
            return false
        }
        //3. 确定单层递归逻辑
        return compareNode(left.left,right.right)&&compareNode(left.right,right.left)
    }

5. 二叉树的最大深度

104

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数后者节点数（取决于高度从0开始还是从1开始）
而根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    // 后序遍历
    // 终止递归条件
    if(!root){
        return 0
    }
    // 确定单层递归逻辑
    let leftHeight=maxDepth(root.left)
    let rightHeight=maxDepth(root.right)
    let height=1+Math.max(leftHeight,rightHeight)
    return height
};

6. 二叉树的最小深度

111

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。，注意是叶子节点。

注意一个重点，不然容易陷入误区：

如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。

反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。

最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。

// 1. 确定递归函数的参数和返回值
var minDepth = function(root) {
    // 2. 确定终止条件
    if(!root){
        return 0
    }
    // 3. 确定单层递归逻辑
    if(root.left===null&&root.right!==null){
        return 1+minDepth(root.right)
    }
    if(root.left!==null&&root.right===null){
        return 1+minDepth(root.left)
    }
    return 1+Math.min(minDepth(root.left),minDepth(root.right))
};

7. 完全二叉树的节点个数

222

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

普通二叉树的解法 , 时间复杂度为O(n)

var countNodes = function(root) {
    if(!root){
        return 0
    }
    return countNodes(root.left)+countNodes(root.right)+1
};

完全二叉树

完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。

对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。

对于情况二，分别递归左，和右，递归到某一深度一定会有左或者右为满二叉树，然后依然可以按照情况1来计算。

/**
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function(root) {
    // 确定终止条件
    if(!root){
        return 0
    }
    // 判断是否为满二叉树，如果是就采用2^深度-1,计算节点数
    let left=0
    let right=0
    let node=root
    while(node){
        left++
        node=node.left
    }
    node=root
    while(node){
        right++
        node=node.right
    }
    if(left==right){
        return (2 ** left)-1 // ** 可以看做是Math.pow（x , y）的语法糖，其作用与Math.pow()一致
    }
    // 确定单层递归逻辑
    return 1+countNodes(root.left)+countNodes(root.right)

};

8. 平衡二叉树

110 易

给定一个二叉树，判断它是否是高度平衡的二叉树。

题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

解析：

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {

    const getBalanced=(root)=>{
        //后序遍历
        // 2. 确定终止条件
        if(!root){
            return 0
        }
        // 3. 确定单层递归逻辑
        let rootLeft=getBalanced(root.left)
        if(rootLeft==-1) return -1
        let rootRight=getBalanced(root.right)
        if(rootRight==-1) return -1
        // 判断是否平衡，若不平衡返回-1，若平衡则返回最大高度
        return Math.abs(rootLeft-rootRight)>1 ? -1 :1+ Math.max(rootLeft,rootRight)
    }
    return  !(getBalanced(root) === -1);
};

9. 二叉树的所有路径

257 简单

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

采用了回溯的算法

/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function(root) {
    // 使用的回溯算法
    let path=[] // 保存每一条路径
    let res=[]  // 保存所有路径
    const dfs=(root,path,res)=>{
        // 先放入经过的节点
        path.push(root.val)
        // 遇到叶子节点，就将路径推入结果
        if(!root.left&&!root.right){
            let temp=path
            res.push(temp.join('->'))
        }
        // 节点存在就遍历
        if(root.left){
            dfs(root.left,path,res)
            // 遍历完后就实行回溯，吐出来遍历过的节点
            path.pop()
        }
        if(root.right){
            dfs(root.right,path,res)
            path.pop()
        }
    }
    dfs(root,path,res)
    return res
};
// 字符串作为参数传递,不符合引用数据类型的规则。即对传进来的值做修改后，不会影响原来的值。(正常情况下，引用数据类型在传递参数时，传的是地址，即形参实参指向同一地址，形参变化会导致实参也变化，但是string例外。)

10. 左叶子之和

404

给定二叉树的根节点 root ，返回所有左叶子之和。

/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumOfLeftLeaves = function(root) {
    let sum=0
    const dfs=(root)=>{
        // 确定终止条件
        if(!root){
            return 
        }
        // 单层递归逻辑
        // 在父节点处判断
        if(root.left&&!root.left.left&&!root.left.right){
            sum+=root.left.val
        }
        dfs(root.left,sum)
        dfs(root.right,sum)
        
    }
    dfs(root)
    return sum
};

11. 找树左下角的值

513

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层最左边 节点的值。

假设二叉树中至少有一个节点。

// 广度优先搜索 层序遍历
//使用广度优先搜索遍历每一层的节点。在遍历一个节点时，需要先把它的非空右子节点放入队列，然后再把它的非空左子节点放入队列，这样才能保证从右到左遍历每一层的节点。广度优先搜索所遍历的最后一个节点的值就是最底层最左边节点的值。

var findBottomLeftValue = function(root) {
    let ret=0
    let queue=[]
    queue.push(root)
    while(queue.length){
        let curNode=queue.shift()
        curNode.right && queue.push(curNode.right)
        curNode.left && queue.push(curNode.left)
        ret=curNode.val
    }
    return ret
};
// 深度优先搜索 递归
// 递归版本：
var findBottomLeftValue = function(root) {
    //首先考虑递归遍历 前序遍历 找到最大深度的叶子节点即可
    let maxPath = 0,resNode = null;
    // 1. 确定递归函数的函数参数
    const dfsTree = function(node,curPath){
    // 2. 确定递归函数终止条件
        if(node.left===null&&node.right===null){
            if(curPath>maxPath){
            maxPath = curPath;
            resNode = node.val;
            }
            // return ;
        }
        node.left&&dfsTree(node.left,curPath+1);// 这里其实有一个回溯的过程
        node.right&&dfsTree(node.right,curPath+1);
    }
    dfsTree(root,1);
    return resNode;
};

12. 路径总和

112

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function(root, targetSum) {
    
    const traversal=(root,targetSum)=>{
        // 遇到叶子节点，并且计数为0
        if(!root.left&&!root.right&&targetSum===0){
        return true
        }
        //  左（空节点不遍历）.若遇到叶子节点返回true，则直接返回true
        if(root.left&&traversal(root.left,targetSum-root.left.val)){
            return true
        }
        //  右（空节点不遍历）.若遇到叶子节点返回true，则直接返回true
        if(root.right&&traversal(root.right,targetSum-root.right.val)){
            return true
        }
        return false
    }
    if(!root) return false
    return traversal(root,targetSum-root.val)
};

13. 从中序与后序遍历序列构造二叉树

106

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

前序和中序可以唯一确定一棵二叉树。

后序和中序可以唯一确定一棵二叉树。

那么前序和后序可不可以唯一确定一棵二叉树呢？

前序和后序不能唯一确定一棵二叉树！

/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function(inorder, postorder) {
    if (!inorder.length) return null;
    const rootVal = postorder.pop(); // 从后序遍历的数组中获取中间节点的值， 即数组最后一个值
    let rootIndex = inorder.indexOf(rootVal); // 获取中间节点在中序遍历中的下标
    const root = new TreeNode(rootVal); // 创建中间节点

    root.left = buildTree(inorder.slice(0, rootIndex), postorder.slice(0, rootIndex)); // 创建左节点
    root.right = buildTree(inorder.slice(rootIndex + 1), postorder.slice(rootIndex)); // 创建右节点
    return root;

};

14. 最大二叉树

654

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

创建一个根节点，其值为 nums 中的最大值。
递归地在最大值左边的 子数组前缀上 构建左子树。
递归地在最大值右边的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树\ 。

/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var constructMaximumBinaryTree = function(nums) {
    // 确定终止条件
    if(!nums.length){
        return null
    }
    // 单层递归逻辑
    let maxval=0
    for(let item of nums){
        if(item>maxval){
            maxval=item
        }
    }
    let index=nums.indexOf(maxval)
    let node=new TreeNode(maxval) // 中
    let leftArr=nums.slice(0,index) // 左
    let rightArr=nums.slice(index+1) // 右
    
    node.left=constructMaximumBinaryTree(leftArr)
    node.right=constructMaximumBinaryTree(rightArr)

    return node
    
};

15. 合并二叉树

617

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

解题思路：

两个二叉树的对应节点可能存在以下三种情况，对于每种情况使用不同的合并方式。

如果两个二叉树的对应节点都为空，则合并后的二叉树的对应节点也为空；

如果两个二叉树的对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点；

如果两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和，此时需要显性合并两个节点。

对一个节点进行合并之后，还要对该节点的左右子树分别进行合并。这是一个递归的过程。

/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {TreeNode}
 */
//  对树1进行改造 返回新的树1
var mergeTrees = function(root1, root2) {
    // 未重叠部分
    if(!root1) return root2
    if(!root2) return root1
    // 重叠部分
    root1.val+=root2.val
    root1.left=mergeTrees(root1.left,root2.left)
    root1.right=mergeTrees(root1.right,root2.right)
    return root1
};

16. 二叉搜索树中的搜索

700

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。

// 递归：

/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function (root, val) {
    if (!root || root.val === val) {
        return root;
    }
    if (root.val > val)
        return searchBST(root.left, val);
    if (root.val < val)
        return searchBST(root.right, val);
};

17. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    let res=[]
    const dfs=(root)=>{
        if(!root) return
        dfs(root.left)
        res.push(root.val)
        dfs(root.right)
    }
    dfs(root)
    for(let i=1;i<res.length;i++){
        if(res[i]<=res[i-1]){
            return false
        }
    }
    return true
};

18. 二叉搜索树中的众树

501

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var findMode = function(root) {
    let count=1
    let maxCount=0
    let pre=null
    let res=[]
    // 使用双指针的方法
    const traversal=(cur)=>{
        // 确定终止条件
        if(!cur) return 
        // 确定单层递归逻辑
        traversal(cur.left)
        if(pre && pre.val==cur.val){
            count++ // 前后指针一样计数加一
        }else{
            count=1 // 新值置1
        }
        pre=cur
        // 如果计数等于最大计数，加入结果数组，但是这里的最大计数不知道是不是真的最大计数
        if(maxCount==count){    
            res.push(cur.val)
        }else if(maxCount<count){
            maxCount=count
            res=[]  // 若不是最大计数，res清空 重新记录
            res.push(cur.val)
        }
        traversal(cur.right)
    }
    traversal(root)
    return res

};

还一种简单的是建立Map哈希表，键为数字，值为出现的次数

19. 二叉树的最近公共祖先

236

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

后序遍历从下往上搜索，类似于回溯

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
  
    // 使用递归的方法
    // 需要从下到上，所以使用后序遍历
    // 1. 确定递归的函数
    const travelTree = function(root,p,q) {
        // 2. 确定递归终止条件
        if(root === null || root === p||root === q) {
            return root;
        }
        // 3. 确定递归单层逻辑
        let left = travelTree(root.left,p,q);
        let right = travelTree(root.right,p,q);
        if(left !== null&&right !== null) {
            return root;
        }
        if(left ===null) {
            return right;
        }else{
            return left;
        }
        
    }
   return  travelTree(root,p,q);
};

20. 二叉搜索树的公共祖先

235

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

只要一个结点在p和q的中间，就是最近公共祖先

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    let ancestor=root
    while(1){
        if(ancestor.val>p.val && ancestor.val>q.val){
            ancestor=ancestor.left
        }else if(ancestor.val<p.val && ancestor.val<q.val){
            ancestor=ancestor.right
        }else{
            return ancestor
        }
    }
};

21.二叉搜索树中插入节点

701

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

思路:只要遍历二叉树，和节点值比较，若小往左子树，若大往右子树，节点不存在时就是插入的位置

/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var insertIntoBST = function(root, val) {
    if(!root){
        return new TreeNode(val)
    }
    if(val<root.val){
       root.left= insertIntoBST(root.left,val)
    }else{
       root.right=insertIntoBST(root.right,val)
    }
    return root

};

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

450

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

思路：

节点可能不存在，返回null
可能为叶子节点，左孩子为空，右也为空返回null
节点左孩子存在，右孩子为空返回左孩子
节点右孩子为空，左孩子存在返回右孩子
几点左右孩子都存在，就将节点左子树移到右子树最左下节点的左孩子位置返回右孩子

/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
var deleteNode = function(root, key) {
    if(!root) return null
    if(root.val===key){
        if(!root.left){
            return root.right
        }else if(!root.right){
            return root.left
        }else{
            let cur=root.right
            while(cur.left){
                cur=cur.left
            }
            cur.left=root.left
            root=root.right
            return root
        }
    }
    if(root.val>key){
        root.left= deleteNode(root.left,key)
    }
    if(root.val<key){
        root.right=deleteNode(root.right,key)
    }
    return root
};

23. 修剪二叉搜索树

669

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

/**
 * @param {TreeNode} root
 * @param {number} low
 * @param {number} high
 * @return {TreeNode}
 */
var trimBST = function(root, low, high) {
    if(!root) return null
    if(root.val<low){
        return trimBST(root.right,low,high) // 如果root（当前节点）的元素小于low的数值，那么应该递归右子树，并返回右子树符合条件的头结点。
    }
    if(root.val>high){
        return trimBST(root.left,low,high) // 同理
    }
    root.left=trimBST(root.left,low,high)
    root.right=trimBST(root.right,low,high)
    return root
};

24. 将有序数组转换为二叉搜索树

108

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。

/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    // 确定递归终止条件
    if(nums.length==0) return null 
    // 确定单层递归逻辑
    let mid=Math.floor(nums.length/2) // 找到中间值
    let node=new TreeNode(nums[mid])
    node.left=sortedArrayToBST(nums.slice(0,mid))
    node.right=sortedArrayToBST(nums.slice(mid+1))
    return node
};

25. 把二叉搜索树转变为累加树

538

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

解题思路：采用右中左遍历，然后用前后指针法

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var convertBST = function(root) {
    let pre=0
    const bfs=(root)=>{
        if(!root) return
        bfs(root.right)
        if(pre){
            root.val+=pre.val
        }
        
        pre=root
        bfs(root.left)
    }
    bfs(root)
    return root
};