Skip to main content

二叉树

二叉树理论基础​

二叉树的种类​
  1. 满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树
  2. 完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。
  3. 二叉搜索树：二叉搜索树是一个有序树。
  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉排序树
  1. 平衡二叉搜索树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
二叉树的储存方式​
  1. 链式存储
  2. 数组存储
二叉树的遍历方式​
  1. 深度优先遍历：先往深走，遇到叶子节点再往回走。
  • 前序遍历：中左右
  • 中序遍历：左中右
  • 后序遍历：左右中
  1. 广度优先遍历：一层一层的去遍历。
  • 层次遍历

二叉树的迭代遍历​

题号

思考

  1. 每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！
  2. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
  3. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
  4. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
方法一​
// 前序遍历
function preorderTraversal(node: TreeNode | null): number[] {
    function traverse(node: TreeNode | null, res: number[]): void {
        if (node === null) return;
        res.push(node.val);
        traverse(node.left, res);
        traverse(node.right, res);
    }
    const res: number[] = [];
    traverse(node, res);
    return res;
}

// 中序遍历
function inorderTraversal(node: TreeNode | null): number[] {
    function traverse(node: TreeNode | null, res: number[]): void {
        if (node === null) return;
        traverse(node.left, res);
        res.push(node.val);
        traverse(node.right, res);
    }
    const res: number[] = [];
    traverse(node, res);
    return res;
}

// 后序遍历
function postorderTraversal(node: TreeNode | null): number[] {
    function traverse(node: TreeNode | null, res: number[]): void {
        if (node === null) return;
        traverse(node.left, res);
        traverse(node.right, res);
        res.push(node.val);
    }
    const res: number[] = [];
    traverse(node, res);
    return res;
}

二叉树遍历迭代法​

题号

思考

  1. 二叉树遍历用迭代法前序和后序是一组，中序不同
方法一​
// 前序遍历（迭代法）
// 入栈 右 -> 左
// 出栈 中 -> 左 -> 右
function preorderTraversal(root: TreeNode | null): number[] {
    if (root === null) return [];
    let res: number[] = [];
    let helperStack: TreeNode[] = [];
    let curNode: TreeNode = root;
    helperStack.push(curNode);
    while (helperStack.length > 0) {
        curNode = helperStack.pop()!;
        res.push(curNode.val);
        if (curNode.right !== null) helperStack.push(curNode.right);
        if (curNode.left !== null) helperStack.push(curNode.left);
    }
    return res;
};

// 中序遍历（迭代法）
// 入栈 左 -> 右
// 出栈 左 -> 中 -> 右

function inorderTraversal(root: TreeNode | null): number[] {
    let helperStack: TreeNode[] = [];
    let res: number[] = [];
    if (root === null) return res;
    let curNode: TreeNode | null = root;
    while (curNode !== null || helperStack.length > 0) {
        if (curNode !== null) {
            helperStack.push(curNode);
            curNode = curNode.left;
        } else {
            curNode = helperStack.pop()!;
            res.push(curNode.val);
            curNode = curNode.right;
        }
    }
    return res;
};

// 后序遍历（迭代法）
// 入栈 左 -> 右
// 出栈 中 -> 右 -> 左 结果翻转
function postorderTraversal(root: TreeNode | null): number[] {
    let helperStack: TreeNode[] = [];
    let res: number[] = [];
    let curNode: TreeNode;
    if (root === null) return res;
    helperStack.push(root);
    while (helperStack.length > 0) {
        curNode = helperStack.pop()!;
        res.push(curNode.val);
        if (curNode.left !== null) helperStack.push(curNode.left);
        if (curNode.right !== null) helperStack.push(curNode.right);
    }
    return res.reverse();
};

二叉树的层序遍历​

题号102. 二叉树的层序遍历

思考

  1. 思路是使用队列来遍历二叉树
方法一 使用for​
function levelOrder(root: TreeNode | null): number[][] {
    let queue = [],
        result = [],
        tmp:number[]=[]
    if(root===null)return []
    queue.push(root)
    let cur:TreeNode
    while(queue.length>0){
        for(let i=0,length=queue.length;i<length;i++){
            cur = queue.shift()!
            tmp.push(cur.val)
            if(cur.left!==null)queue.push(cur.left)
            if(cur.right!==null)queue.push(cur.right)
        }
        result.push(tmp)
        tmp =[]
    }
    return result
};
方法二 使用while​
function levelOrder(root: TreeNode | null): number[][] {
    let result = [],
        tmp = [],
        helpQueue = [],
        cur
    if(root===null)return []
    helpQueue.push(root) //入节点进队列
    while(helpQueue.length>0){  //二叉树的一层循环
        let size = helpQueue.length //设定一层遍历
        while(size--){
            cur = helpQueue.shift()
            tmp.push(cur.val)  //出一个节点
            if(cur.left!==null)helpQueue.push(cur.left) //判断是否为空
            if(cur.right!==null)helpQueue.push(cur.right)
        }
        result.push(tmp)
        tmp = []
    }
    return result
};

翻转二叉树​

题号226. 翻转二叉树

思考

  1. 一开始使用层序遍历也做出来了
  2. 使用递归，注意中序遍历的不同
方法一 层序遍历​
function invertTree(root: TreeNode | null): TreeNode | null {
    let queue = []
    if(root===null)return null
    queue.push(root)
    while(queue.length>0){
        for(let i=0,length=queue.length;i<length;i++){
            let cur = queue.shift(),
                tmp = cur.left
                cur.left = cur.right
                cur.right = tmp
                tmp = null

            if(cur.left!==null){
                queue.push(cur.left)
            }
            if(cur.right!==null){
                queue.push(cur.right)
            }
        }
    }
    return root
};
方法二 递归​
// 前序遍历
function invertTree(root: TreeNode | null): TreeNode | null {
    function reverse(cur){
        if(cur===null)return cur
        if(cur!==null)[cur.left,cur.right] = [cur.right,cur.left]
        reverse(cur.left)
        reverse(cur.right)
    }
    reverse(root)
    return root
};

// 后序遍历
function invertTree(root: TreeNode | null): TreeNode | null {
    function reverse(cur){
        if(cur===null)return cur
        reverse(cur.left)
        reverse(cur.right)
        if(cur!==null)[cur.left,cur.right] = [cur.right,cur.left]
    }
    reverse(root)
    return root
};

// 中序遍历
function invertTree(root: TreeNode | null): TreeNode | null {
    function reverse(cur){
        if(cur===null)return cur
        reverse(cur.left)
        if(cur!==null)[cur.left,cur.right] = [cur.right,cur.left]
        reverse(cur.left)  //要注意这边还是翻转left，中序遍历与前面两个不同的地方
    }
    reverse(root)
    return root
};

对称二叉树​

题号101. 对称二叉树

思考

  1. 要判断是否对称也就是能不能翻转
  2. 因为要先比较下面的子节点一步一步往上退所以只能用后序
方法一 后序递归​
function isSymmetric(root: TreeNode | null): boolean {
    function compare(left,right){
        if(left===null&&right!==null)return false
        else if(left!==null&&right===null)return false
        else if(left===null&&right===null)return true
        else if(left.val!==right.val)return false
        else if(left!==null&&right!==null){
           let outside=  compare(left.left,right.right),
                inside = compare(left.right,right.left)
        return  outside&&inside
            
        }
    }
    return compare(root.left,root.right)

};

二叉树的最大深度​

题号104. 二叉树的最大深度

类似题559. N 叉树的最大深度

理解题意​
  1. 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数
  2. 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数

思考

  1. 最开始想到用迭代法
  2. 递归法，因为要求的是深度所以从叶节点向根节点一直加，所以想到用后序遍历，因为要先达到根节点嘛
  3. 递归还是不太熟练需要多练习
方法一 迭代法​
function maxDepth(root: TreeNode | null): number {
    let queue = [],
        deep=0,
        cur:TreeNode
    if(root===null)return 0
    queue.push(root)
    while(queue.length>0){
        for(let i=0,length=queue.length;i<length;i++){
            cur = queue.shift()!
            if(cur.left!==null)queue.push(cur.left)
            if(cur.right!==null)queue.push(cur.right)
        } //每一层结束后进行一次深度++
        deep++
    }
    return deep
};
方法二 递归法​
function maxDepth(root: TreeNode | null): number {
  //使用递归的方法 递归三部曲
    //1. 确定递归函数的参数和返回值
    function getdepth(node) {
    //2. 确定终止条件
        if(node === null) {
            return 0;
        }
    //3. 确定单层逻辑
        let leftdepth = getdepth(node.left);
        let rightdepth = getdepth(node.right);
        let depth = 1 + Math.max(leftdepth, rightdepth);
        return depth;
    }
    return getdepth(root);
};

二叉树的最小深度​

题号111. 二叉树的最小深度

思考

  1. 层序遍历，当节点的left和right都不存在的时候返回这个深度
方法一 层序遍历​
function minDepth(root: TreeNode | null): number {
 let queue = [],
        deep=1,
        cur:TreeNode
    if(root===null)return 0
    queue.push(root)
    while(queue.length>0){
        for(let i=0,length=queue.length;i<length;i++){
            cur = queue.shift()!
            if(cur.left!==null)queue.push(cur.left)
            if(cur.right!==null)queue.push(cur.right)
            if(cur.left===null&&cur.right===null)return deep++
        }
        deep++
    }
};
方法二 递归​
function minDepth(root: TreeNode | null): number {
    if(!root) return 0;
    // 到叶子节点 返回 1
    if(!root.left && !root.right) return 1;
    // 只有右节点时 递归右节点
    if(!root.left) return 1 + minDepth(root.right);
    // 只有左节点时 递归左节点
    if(!root.right) return 1 + minDepth(root.left);
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
};

完全二叉树的节点个数​

题号222. 完全二叉树的节点个数

思考

  1. 当成普通二叉树方法
  2. 层序遍历
  3. 递归遍历
  4. 完全二叉树的特性
  5. 完全二叉树有一部分是满二叉树，而满二叉树有一个公式求节点数量 2^树深度 - 1

思路

使用完全二叉树特性完成

  1. 先搜索外侧（也就是左右两边）
  2. 如果left===right就意味着是一个满二叉树，套公式返回
  3. 不是再度细分进入下一层，重新完成这个逻辑

重点在于递归的理解以及每次进入下一层都要补一个一进去

递归思路

  1. 确定参数以及函数返回值

    这里入参是节点，返回节点数量

  2. 确定终止条件

    如果为空节点的话就返回0，如果是满二叉树的话就终止并且返回节点数目

  3. 确定单层递归的逻辑

    和普通的思路一样

方法一 普通二叉树 解法​
//迭代法 
function countNodes(root: TreeNode | null): number {
    let queue = [],count=0
    if(root!==null)queue.push(root)
    while(queue.length>0){
        for(let i=0,length=queue.length;i<length;i++){
            let cur = queue.shift()
            count++
            if(cur.left!==null)queue.push(cur.left)
            if(cur.right!==null)queue.push(cur.right)
        }
    }
    return count
};
//递归法
function countNodes(root: TreeNode | null): number {
    function getCount(cur):number{
        if(cur===null)return 0
        let left = getCount(cur.left)
        let right = getCount(cur.right)
        if(cur!==null)return left+right+1
    }
    return getCount(root)
};
方法二 完全二叉树特性解法​
function countNodes(root: TreeNode | null): number {
    // 终止条件
    if(root===null)return 0
    let left = 0,right = 0,cur = root
    while(cur!==null){
        left++
        cur = cur.left
    }
    cur = root
    while(cur!==null){
        right++
        cur = cur.right
    }
    if(left===right){
        return (2<<left-1)-1
    }
    // 单层递归逻辑
    return countNodes(root.left)+countNodes(root.right)+1
};

平衡二叉树​

题号110. 平衡二叉树

思考

  1. 死活没想出来迭代法怎么做。。。
  2. 有递归的思路，也知道是后序写法但是没写出来

思路

  1. 要从叶节点一步一步判断到根节点，所以是用后序遍历
  2. 高度相减不大于1就是平衡二叉树，返回的时候也是返回最大的那个高度
  3. 有一个节点不满足就不是平衡二叉树，传递结果就可以了
方法一 后序递归​
function isBalanced(root: TreeNode | null): boolean {
    function get(cur):number{
        // 确定终止条件
        if(cur===null)return 0
        // 开始执行单层操作
        // 获得左高度
        let left = get(cur.left)
        if(left===-1)return -1 //失败的传递
        // 获得右高度
        let right = get(cur.right)
        if(right===-1)return -1

        // 计算左右子树之差判定该节点是否为平衡二叉树

        if(Math.abs(left-right)>1)return -1
        else return Math.max(left,right)+1//记住要加一因为要把这个节点的高度也加上去
    }
    return !(get(root)===-1)
};

二叉树的所有路径​

题号257. 二叉树的所有路径

思考

  1. 因为要一步一步往叶节点走，所以用前序来做
  2. 视频里提到回溯，但是由于我们是直接传string是值传递所以不用考虑到这个
方法一​
function binaryTreePaths(root: TreeNode | null): string[] {
    let result = []
    //1. 确定递归函数 函数参数
    function get(cur,curPath){
     //2. 确定终止条件，到叶子节点就终止
        if(cur.left===null&& cur.right===null){
            curPath+=cur.val
            result.push(curPath)
            return
        }
        //3. 确定单层递归逻辑
        curPath += cur.val+'->' // 中
        if(cur.left!==null)get(cur.left,curPath) // 左
        if(cur.right!==null)get(cur.right,curPath)  // 右
    }
    get(root,'')
    return result
};
方法二​
function binaryTreePaths(root: TreeNode | null): string[] {
    function recur(cur:TreeNode,route:string,resArr:string[]):void{
        route+=String(cur.val)
        if(cur.left===null&&cur.right===null){
            resArr.push(route)
            return
        }
        if (cur.left !== null) recur(cur.left, route + '->', resArr);
        if (cur.right !== null) recur(cur.right, route + '->', resArr);
    }
    const resArr = []
    if(root===null)return resArr
    recur(root,'',resArr)
    return resArr
};

左叶子之和​

题号404. 左叶子之和

思考

  1. 第一反应用迭代法
  2. 后序递归
方法一 迭代法​

function sumOfLeftLeaves(root: TreeNode | null): number {
    let queue = [],sum =0
    if(root!==null)queue.push(root)
    while(queue.length>0){
        for(let i=0,length=queue.length;i<length;i++){
            let cur = queue.shift()
            if(cur.left!==null&&cur.left.left===null&&cur.left.right===null)sum+=cur.left.val
            if(cur.left!==null)queue.push(cur.left)
            if(cur.right!==null)queue.push(cur.right)
        }
    }
    return sum
};
方法二 递归法​
function sumOfLeftLeaves(root: TreeNode | null): number {
    if(root===null)return 0
    // if(root.left===null&&root.right===null)return 0
    let left = sumOfLeftLeaves(root.left)
    let right = sumOfLeftLeaves(root.right)
    if(root.left!==null&&root.left.left===null&&root.left.right===null){
        left = root.left.val
    }
    return left+right
};

找树左下角的值​

题号513. 找树左下角的值

思考

  1. 这道题目一开始想到用层序来做，找到最后一层返回左边第一个就行了
  2. 递归的话重要的是理解如何找到左下第一个，需要记录一个depth，如果是引用类型的需要回溯，值拷贝的话就不需要了，隐藏了回溯的过程
方法一 层序遍历​
function findBottomLeftValue(root: TreeNode | null): number {
    let queue = [],result=[],tmp=[]
    if(root!==null)queue.push(root)
    while(queue.length>0){
        for(let i=0,length=queue.length;i<length;i++){
            let cur = queue.shift()
            tmp.push(cur.val)
            if(cur.left!==null)queue.push(cur.left)
            if(cur.right!==null)queue.push(cur.right)
        }
        result.push(tmp)
        tmp = []
    }
    return result[result.length-1][0]
};
方法二 递归​

function findBottomLeftValue(root: TreeNode | null): number {
    //首先考虑递归遍历 前序遍历 找到最大深度的叶子节点即可
    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;
            }
        }
        node.left && dfsTree(node.left, curPath+1);
        node.right && dfsTree(node.right, curPath+1);
    }
    dfsTree(root,1);
    return resNode;
};

路径总和​

题号112. 路径总和

配合113. 路径总和 II理解

思考

  1. 这道题目要理解什么时候需要把返回值传递回去
  2. 再来看返回值，递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点
  • 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii）
  • 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先 (opens new window)中介绍）
  • 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（本题的情况）
方法一​
function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    function get(cur,count){
        if(cur.left===null&&cur.right===null){
            if(count===0)return true
            else return false
        }
        if(cur.left!==null&&get(cur.left,count-cur.left.val))return true
        if(cur.right!==null&&get(cur.right,count-cur.right.val))return true
        return false
    }
    if(root===null)return false
    return get(root,targetSum-root.val)
};

113. 路径总和 II

方法一​
function pathSum(root: TreeNode | null, targetSum: number): number[][] {
    // 递归法，要遍历整个树找到所有路径所以不需要返回值
    let result = []
    function get(cur,count,route){
        // 找到叶子节点，且和为target的值
        if(count===0&&cur.left===null&&cur.right===null){
            result.push([...route]) //不能写route，要浅拷贝，否则之后route值改变result里面的值也会改变
            return
        }
        if(cur.left===null&&cur.right===null)return
        if(cur.left){
            route.push(cur.left.val)
            get(cur.left,count-cur.left.val,route) // 递归
            route.pop() // 回溯
        }
        if(cur.right){
            route.push(cur.right.val)
            get(cur.right,count-cur.right.val,route) // 递归
            route.pop() // 回溯
        }
        return
    }
    if(root===null)return []
    get(root,targetSum-root.val,[root.val]) // 把根节点放进路径
    return result
};

从中序和后序遍历序列构造二叉树​

题号106. 从中序与后序遍历序列构造二叉树

相关题目105. 从前序与中序遍历序列构造二叉树

思考

来看一下一共分几步：

  • 第一步：如果数组大小为零的话，说明是空节点了。
  • 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
  • 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
  • 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
  • 第五步：切割后序数组，切成后序左数组和后序右数组
  • 第六步：递归处理左区间和右区间
从中序和后序遍历序列构造二叉树​
function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
    if(postorder.length===0)return null //如果数组大小为0说明是空节点了
    let value = postorder.pop()  // 获得后序遍历最后一个元素也就是中，然后删除它
    let root = new TreeNode(value) //root
    let index = inorder.indexOf(value)  // 找到中在中序遍历中的位置

    let leftInorder = inorder.slice(0,index),rightInorder = inorder.slice(index+1) //分割中序数组 因为中在中序数组里面所以要+1
    let leftPostorder = postorder.slice(0,index),rightPostorder = postorder.slice(index) //分割后序数组 slice是左开右闭的
    root.left = buildTree(leftInorder,leftPostorder)
    root.right = buildTree(rightInorder,rightPostorder)
    return root
};
从前序与中序遍历序列构造二叉树​
function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    if(preorder.length===0)return null
    let value = preorder.shift()
    let index = inorder.indexOf(value)
    let root = new TreeNode(value)

    root.left = buildTree(preorder.slice(0,index),inorder.slice(0,index))
    root.right = buildTree(preorder.slice(index),inorder.slice(index+1))
    return root
};

构造最大的二叉树​

题号654. 最大二叉树

思考

  1. 凡是用到构造二叉树的题目都要用到前序遍历（中左右）
方法一​
function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
    if(nums.length===0)return null
    let max = Math.max(...nums)
    let index = nums.indexOf(max)
    let root = new TreeNode(max)
    root.left = constructMaximumBinaryTree(nums.slice(0,index))
    root.right = constructMaximumBinaryTree(nums.slice(index+1))
    return root
};

合并二叉树​

题号617. 合并二叉树

思考

  1. 这题考点在于同时操作两个二叉树
  2. 有新建和不新建两种写法
方法一 不新建​
function mergeTrees(root1: TreeNode | null, root2: TreeNode | null): TreeNode | null {
    if(root1===null)return root2
    if(root2===null)return root1
    root1.val+=root2.val
    root1.left = mergeTrees(root1.left,root2.left)
    root1.right = mergeTrees(root1.right,root2.right)
    return root1
};
方法二 新建二叉树​
function mergeTrees(root1: TreeNode | null, root2: TreeNode | null): TreeNode | null {
    if(root1===null)return root2
    if(root2===null)return root1
    let root = new TreeNode(0)
    root.val = root1.val + root2.val
    root.left = mergeTrees(root1.left,root2.left)
    root.right = mergeTrees(root1.right,root2.right)
    return root
};

二叉搜索树中的搜索​

题号700. 二叉搜索树中的搜索

思考

  1. 二叉搜索树的特性，二叉搜索树是一个有序树：
  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉搜索树
  1. 递归法
  2. 迭代法 因为二叉搜索树是有顺序的所以不需要再用队列模拟递归了
方法一 递归法​
function searchBST(root: TreeNode | null, val: number): TreeNode | null {
    if(root===null||root.val===val)return root
    let result = null
    if(root.val>val)result = searchBST(root.left,val)
    if(root.val<val)result = searchBST(root.right,val)
    return result
};
方法二 迭代法​
function searchBST(root: TreeNode | null, val: number): TreeNode | null {
    while(root!==null){
        if(root.val<val)root = root.right
        else if (root.val>val)root = root.left
        else return root
    }
    return null
};

验证二叉搜索树​

题号98. 验证二叉搜索树

思考

  1. 一开始陷入了一个误区，不是节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。就是二叉树还需要满足所有左子树和右子树自身必须也是二叉搜索树。
  2. 递归法，需要使用中序遍历，可以设置一个最小值来记录root，也可以使用双指针pre
  3. 辅助数组解法

思路

  1. 要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。
方法一 递归法优化双指针​
function isValidBST(root: TreeNode | null): boolean {
    let pre = null
    function get(root){
        if(root===null)return true
        let left = get(root.left)
        if(pre!==null&&pre.val>=root.val)return false
        pre = root
        let right = get(root.right)
        return left&&right
    }
    return get(root)
};
方法二 辅助数组解法​
function isValidBST(root: TreeNode | null): boolean {
    let result = []
    function get(root){
        if(root===null)return
        get(root.left)
        result.push(root.val)
        get(root.right)
    }
    get(root)
    for (let i = 1; i < result.length; i++) {
    // 注意要小于等于，搜索树里不能有相同元素
    if (result[i] <= result[i - 1]) return false;
    }
    return true;
};

二叉搜索树的最小绝对差​

题号530. 二叉搜索树的最小绝对差

思考

  1. 双指针，由于二叉搜索树中序遍历是有序的所以都是相邻的相减
function getMinimumDifference(root: TreeNode | null): number {
    let pre = null,min = +Infinity
    function get(cur){
        if(cur===null)return 
        get(cur.left)
        if(pre!==null)min =  Math.min(min,cur.val-pre.val)
        pre = cur
        get(cur.right)
    }
    get(root)
    return min
};

二叉搜索树中的众树​

题号501. 二叉搜索树中的众数

思考

  1. 一开始想到之前做数组中找众数使用Map，同理也可以
  2. 但是二叉搜索树是有序的，可以优化

思路

  1. 用一个数组来记录结果，maxCount和count来记录出现的次数，再用双指针
  2. 中序递归是有序的，中间层处理是要是count>maxCount就意味着原先的不是众数清空result重新塞入
方法一 Map法​
function findMode(root: TreeNode | null): number[] {
    let result = new Map()
    function get(cur){
        if(cur===null)return
        get(cur.left)
        result.set(cur.val,result.get(cur.val)+1||1)
        get(cur.right)
    }
    get(root)
    let maxCount = result.get(root.val);
    // 定义一个存放结果的数组res
    let res = [];
    for(let [key,value] of result) {
        // 如果当前值等于最大出现次数就直接在res增加该值
        if(value === maxCount) {
            res.push(key);
        }
        // 如果value的值大于原本的maxCount就清空res的所有值，因为找到了更大的
        if(value>maxCount) {
            res = [];
            maxCount = value;
            res.push(key);
        }
    }
    return res;
};
方法二 递归中序​
function findMode(root: TreeNode | null): number[] {
    let result=[],pre=null,
        count=0,maxCount=1
    function get(cur){
        if(cur===null)return      
        get(cur.left)
        if(pre===null)count=1  // 第一个节点
        else if(pre.val===cur.val)count++ //如果相等计数加一
        else count=1  // 不相等重置计数
        
        if(count===maxCount)result.push(cur.val)
        else if(count>maxCount){
            result = []
            maxCount = count
            result.push(cur.val)
        }
        pre = cur  //移动pre
        get(cur.right)
    }
    get(root)
    return result
};

二叉树的最近公共祖先​

题号236. 二叉树的最近公共祖先

思考

  1. 使用后序递归就可以实现回溯
方法一​

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
    function get(cur,p,q){
        if(cur===null)return null
        if(cur===p||cur===q)return cur
        let left = get(cur.left,p,q)
        let right = get(cur.right,p,q)
        if(left!==null&&right!==null)return cur  
        if(left===null&&right!==null)return right
        else if(left!==null&&right===null) return left
        else return null
    }
    return get(root,p,q)
};

二叉搜索树的最近公共祖先​

题号235. 二叉搜索树的最近公共祖先

思考

  1. 这道题目用二叉树的最近公共祖先也能过，但是有更优的解法
  2. 利用好二叉搜索树是有序的这个特性
  3. 有点像三数之和那个思想
  4. 迭代法也很简单，因为是有序的
方法一 递归​
function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
    if(root===null)return null
    if(root.val>q.val&&root.val>p.val){
        return  lowestCommonAncestor(root.left,p,q)
    }else if(root.val<q.val&&root.val<p.val){
        return  lowestCommonAncestor(root.right,p,q)
    }else{
        return root  
    }
};
方法二 迭代法​
function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
    while(root){
        if(root.val>q.val&&root.val>p.val)root = root.left
        else if(root.val<q.val&&root.val<p.val)root = root.right
        else return root
    }
};

二叉搜索树中的插入操作​

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

思考

  1. 都在叶节点实现插入就可以了
  2. 递归
方法一 递归法​
function insertIntoBST(root: TreeNode | null, val: number): TreeNode | null {
    if(root===null){
        let newNode = new TreeNode(val)
        return newNode
    }
    if(root.val>val){
        root.left = insertIntoBST(root.left,val)
    }
    if(root.val<val){
        root.right = insertIntoBST(root.right,val)
    }
    return root
};

删除二叉搜索树中的节点

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

思考

  1. 要思考删除需要分五种情况
  2. 没有找到删除的节点：return null
  3. 删除的是叶节点: 直接删除
  4. 删除的节点左子树为空：删除节点右子树顶上
  5. 删除的节点右子树为空：删除节点左子树顶上
  6. 删除的节点左右子树都不为空
  7. 左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点
方法一​
function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
    function get(root,key){
        if(root===null)return null   // 没找到
        if(root.val===key){  // 找到了
            if(root.left===null&&root.right===null)return null // 为叶节点
            else if(root.left===null)return  root.right // 左子树是空的
            else if(root.right===null)return root.left  // 右子树是空的
            let cur = root.right   // 左右子树都不是空的，记录右树
            while(cur.left!==null){  //找到右树中最小的
                cur = cur.left
            }
            cur.left = root.left  // 把左子树赋值给右树中最小的
            return root.right  //返回右树
        }
        if(root.val>key)root.left = get(root.left,key)
        if(root.val<key)root.right = get(root.right,key)
        return root
    }
    return get(root,key)
};

修建二叉树​

题号669. 修剪二叉搜索树

思考

  1. 由于是二叉搜索树，所以是有序的。
  2. 比low小的时候左树肯定比low小，那就看右树
  3. 比high大的时候右树肯定比high大，那就看左数
方法一 递归​
function trimBST(root: TreeNode | null, low: number, high: number): TreeNode | null {
    if(root===null)return null
    if(root.val<low){   // 比low小的时候左树肯定比low小，那就看右树
        return trimBST(root.right,low,high)
    }
    if(root.val>high){    // 比high大的时候右树肯定比high大，那就看左数
        return trimBST(root.left,low,high)
    }
    root.left = trimBST(root.left,low,high)
    root.right = trimBST(root.right,low,high)
    return root
};

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

题号108. 将有序数组转换为二叉搜索树

思考

  1. 本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。
方法一 递归法​
function sortedArrayToBST(nums: number[]): TreeNode | null {
    function buildTree(arr,left,right){
        if(left>right)return null
        
        let mid = Math.floor(left+(right-left)/2)
        let root = new TreeNode(arr[mid])
        root.left = buildTree(arr,left,mid-1)
        root.right = buildTree(arr,mid+1,right)
        return root
    }
    return buildTree(nums,0,nums.length-1)
};

把二叉搜索树转换为累加树​

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

思考

  1. 二叉搜索树是一个有序数组这样就能理解了
function convertBST(root: TreeNode | null): TreeNode | null {
    let pre: number = 0;
    function recur(root: TreeNode | null): void {
        if (root === null) return;
        recur(root.right);
        root.val += pre;
        pre = root.val;
        recur(root.left);
    }
    recur(root);
    return root;
};