3.5w字 | 47道 LeetCode 题目带你看看二叉树的那些套路（下）

前言：

周末无聊，整理了一下之前做过的LeetCode上的二叉树相关的题目，也方便以后不断回顾，LeetCode的题目总是刷完之后感觉会了，过一段时间又忘了，还是要不断复盘。

全文约3.5w字，共47道题目，建议收藏慢慢看，有不对的地方欢迎大家指正！

掘金发文章有字数限制，所以分成了两篇，本文为下篇 欢迎关注之后的更新！

5. 经典题目：二叉树的操作

（1）翻转二叉树

翻转一棵二叉树。示例：

输入：
     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：
     4
   /   \
  7     2
 / \   / \
9   6 3   1

通过翻转之后，二叉树的每一个左右子孩子都发生了交换，所有可以使用递归来实现：遍历每一个结点，并将每一个结点的左右孩子进行交换。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
   if(!root){
       return root
   }
   // 递归获取左右子结点
   let right = invertTree(root.right)
   let left = invertTree(root.left)
   // 交换左右子结点
   root.right = left
   root.left =right
   return root
};

复杂度分析：

• 时间复杂度：O(N)，其中 N 为二叉树节点的数目。需要遍历二叉树中的每一个节点，对每个节点而言，在常数时间内交换其两棵子树。
• 空间复杂度：O(N)。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(logN)。而在最坏情况下，树形成链状，空间复杂度为 O(N)。

（2）合并二叉树

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。示例 1:

输入: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

注意: 合并必须从两个树的根节点开始。

这里可以使用递归的方式来计算，保持t1不便，将t2的节点往t1上加就可以了。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} t1
 * @param {TreeNode} t2
 * @return {TreeNode}
 */
var mergeTrees = function(t1, t2) {
    if(!t1 && t2){
        return t2
    }
    if(t1 && !t2 || !t1 && !t2){
        return t1
    }

    t1.val += t2.val
    t1.left = mergeTrees(t1.left, t2.left)
    t1.right = mergeTrees(t1.right, t2.right)
    return t1
};

复杂度分析：

• 时间复杂度：O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点个数。对两个二叉树同时进行深度优先搜索，只有当两个二叉树中的对应节点都不为空时才会对该节点进行显性合并操作，因此被访问到的节点数不会超过较小的二叉树的节点数。
• 空间复杂度：O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点个数。空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数。

（3）二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [0]
输出：[0]

提示：

• 树中结点数在范围 [0, 2000] 内
• -100 <= Node.val <= 100

进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

题目中也说了，展开后的单链表与二叉树 先序遍历 顺序相同，所以我们可以先对二叉树进行先序遍历，然后将遍历的结果置位一条链表。这个链表相当于左子节点都是null，右子节点都是二叉树的值的二叉树。**

/**
 * 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 {void} Do not return anything, modify root in-place instead.
 */
var flatten = function(root) {
    // 前序遍历
    const fn = (root) => {
        if(!root){
            return 
        }
        res.push(root)
        fn(root.left)
        fn(root.right)
    }

    let res = []
    fn(root)
    for(let i = 0; i < res.length - 1; i++){
        res[i].left = null
        res[i].right = res[i + 1]
    }
};

复杂度分析：

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。前序遍历的时间复杂度是 O(n)，前序遍历之后，需要对每个节点更新左右子节点的信息，时间复杂度也是 O(n)。
• 空间复杂度：O(n)，其中 n 是二叉树的节点数。空间复杂度取决于栈（递归调用栈或者迭代中显性使用的栈）和存储前序遍历结果的列表的大小，栈内的元素个数不会超过 n，前序遍历列表中的元素个数是 n。

（4）从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。**注意：**你可以假设树中没有重复的元素。例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

先看下前序遍历和中序遍历的规律：

• 前序遍历：根节点 + 左子树前序遍历 + 右子树前序遍历
• 中序遍历：左子树中序遍历 + 根节点 + 右字数中序遍历

可以根据上面获得根据点判断，哪些是左子节点，哪些是右子节点，依次这样判断即可。

实现步骤如下：

• 前序遍历找到根结点root
• 找到root在中序遍历的位置 -> 左子树的长度和右子树的长度
• 截取左子树的中序遍历、右子树的中序遍历
• 截取左子树的前序遍历、右子树的前序遍历
• 递归重建二叉树

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    if(!inorder.length) return null
    let tmp = preorder[0]
    let mid = inorder.indexOf(tmp)
    
    let root = new TreeNode(tmp)
    root.left = buildTree(preorder.slice(1,mid+1),inorder.slice(0,mid))
    root.right = buildTree(preorder.slice(mid+1),inorder.slice(mid + 1))
    return root
};

复杂度分析：

• 时间复杂度：O(n)，其中 n 是树中的节点个数。
• 空间复杂度：O(n)，除去返回的答案需要的 O(n) 空间之外，还需要使用 O(n) 的空间存储哈希映射，以及 O(h)（其中 h 是树的高度）的空间表示递归时栈空间。这里 h<n，所以总空间复杂度为 O(n)。

（5）从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。注意：你可以假设树中没有重复的元素。例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

先看下中序遍历和后序遍历的规律：

• 中序遍历：左子树中序遍历 + 根节点 + 右字数中序遍历
• 后序遍历：左子树后序遍历 + 右子树后序遍历 + 根节点

这个题目的思路也是使用递归：

• 可以看到，后序遍历数组的最后一个值是二叉树的根节点，也就是示例中的7
• 根据根节点的值，在中序遍历的数组中找到该值的索引，我就可以知道，3左边的是左子树的中序遍历的数组，3后面的是右子树的中序遍历的数组
• 根据根节点的值，在后续遍历数组中找到的该值得索引，就可以知道，0到该索引的的值都是左子树的后序遍历的数组，后面的数值就是右子树的后序遍历的数组（需要排除根节点）
• 根据上面得到的左右子树的中序遍历和后续遍历的结果进行递归操作

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function(inorder, postorder) {
    if(!inorder.length) return null
    let len = postorder.length
    let tmp = postorder[len-1]
    let mid = inorder.indexOf(tmp)
    
    let root = new TreeNode(tmp)
    root.left = buildTree(inorder.slice(0,mid), postorder.slice(0,mid))
    root.right = buildTree(inorder.slice(mid + 1), postorder.slice(mid,len-1))
    return root
};

复杂度分析：

• 时间复杂度：O(n)，其中 n 是树中的节点个数。
• 空间复杂度：O(n)，除去返回的答案需要的 O(n) 空间之外，还需要使用 O(n) 的空间存储哈希映射，以及 O(h)（其中 h 是树的高度）的空间表示递归时栈空间。这里 h<n，所以总空间复杂度为 O(n)。

（6）从前序与后序遍历序列构造二叉树

返回与给定的前序和后序遍历匹配的任何二叉树。其中，pre 和 post 遍历中的值是不同的正整数。示例：

输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

提示：

• 1 <= pre.length == post.length <= 30
• pre[] 和 post[] 都是 1, 2, …, pre.length 的排列
• 每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。

先看下前序遍历和后序遍历的规律：

• 前序遍历：根节点 + 左子树前序遍历 + 右子树前序遍历
• 后序遍历：左子树后序遍历 + 右子树后序遍历 + 根节点

这个题目的思路也是使用递归：

• 根据前序遍历的特点，就可以知道1是二叉树的根节点，那么紧跟其后的应该就是左节点，也就是2。
• 在后序遍历中找到2对应的位置，我们就可以知道2及之前的数都是该二叉树的左节点的后序遍历数组，之后的数都是二叉树的右节点的后序遍历数组（需要除去根节点）
• 根据左子树的长度在先序遍历中找到左子树和右子树的前序遍历值。
• 进行递归操作，得出最后的二叉树。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} pre
 * @param {number[]} post
 * @return {TreeNode}
 */
var constructFromPrePost = function(pre, post) {
    if(!pre.length) return null
    let tmp = pre[0];
    let index = post.indexOf(pre[1]);
    let root = new TreeNode(tmp);
    
    root.left = constructFromPrePost(pre.slice(1,index+2),post.slice(0,index+1));
    root.right = constructFromPrePost(pre.slice(index+2),post.slice(index+1,post.length-1));
    return root;
};

复杂度分析：

• 时间复杂度：O(n)，其中 n 是树中的节点个数。
• 空间复杂度：O(n)，除去返回的答案需要的 O(n) 空间之外，还需要使用 O(n) 的空间存储哈希映射，以及 O(h)（其中 h 是树的高度）的空间表示递归时栈空间。这里 h<n，所以总空间复杂度为 O(n)。

（7）填充每个节点的下一个右侧节点指针

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。

示例：

输入：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

输出：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}

解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。

提示：

• 你只能使用常量级额外空间。
• 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度

这里我们使用递归的方式来解决这个问题。我们对二叉树进行先序遍历。我们要讨论两种情况：同一父节点的左右节点相连 和 非同一父节点的左右节点相连，下面来看以下：

• 第一步，对于同一父节点的左右节点相连，将左节点的值指向右节点
• 第二部，对于非同一父节点的左右节点相连，以图中的5和6为例，我们通过5的父节点2，找到他的右节点3，再通过3找到其左节点，并将5和相连3相连。

对于上面的步骤，进行递归，直至遍历完所有的节点。

/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */

/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function(root) {
    if(!root) return null
	// 同一父节点的左右节点相连
    if(root.left && root.right){
        root.left.next = root.right
    }
	// 非同一父节点的左右节点相连
    if(root.right && root.next && root.next.left){
        root.right.next = root.next.left
    }
	// 递归遍历
    connect(root.left)
    connect(root.right)
    return root
};

复杂度分析：

• 时间复杂度：O(N)，其中n是二叉树的节点的数量，每个节点只访问一次。

• 空间复杂度：O(1)，不需要存储额外的节点。

（8）填充每个节点的下一个右侧节点指针 II

给定一个二叉树：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。

进阶：

• 你只能使用常量级额外空间。
• 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

示例：

输入：root = [1,2,3,4,5,null,7] 输出：[1,#,2,3,#,4,5,7,#] 解释： 给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。

提示：

• 树中的节点数小于 6000
• -100 <= node.val <= 100

对于这道题目，我们可以对树进行层序遍历，树的层序遍历是基于广度优先遍历的，按照层的顺序进行遍历，我们需要舒适话一个队列queue，这个队列中保存着当前层的节点。

当队列不为空的时候就记录当前队列的的长度len，当遍历这一层的时候，修改这一层节点的 next 指针，这样就可以把每一层都组织成链表。

/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */

/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function(root) {
    if (!root) {
        return null;
    }
    const queue = [root];
    while (queue.length) {
        const len = queue.length;
        let last = null;
        for (let i = 1; i <= len; ++i) {
            let node = queue.shift();
            if (node.left) {
                queue.push(node.left);
            }
            if (node.right) {
                queue.push(node.right);
            }
            if (i !== 1) {
                last.next = node;
            }
            last = node;
        }
    }
    return root;
};

复杂度分析：

• 时间复杂度：O(N)。其中N是树的节点数，我们需要遍历这棵树上所有的点，时间复杂度为 O(N)。
• 空间复杂度：O(N)。其中N是树的节点数，我们需要初始化一个队列，它的长度最大不超过树的节点数。

（9）二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例:你可以将以下二叉树：

    1
   / \
  2   3
     / \
    4   5
    
序列化为 "[1,2,3,null,null,4,5]"

提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。

对于这道二叉树的题目，我们能想到的最直接的方式就是深度优先宾利和广度优先遍历，这里就分别用两种方式来解答。

深度优先遍历：

• 首先是序列化二叉树，可以定义一个遍历方法，先访问根节点，再访问左节点，最后访问右节点，将每个节点的值都存入数组，如果是null也要存入数组。
• 之后是反序列化二叉树，也就是将数组转化为二叉树，因为数组是二叉树先序遍历的结果，所以我们就可以遍历数组，然后按照根节点、左子树、右子树的顺序复原二叉树

广度优先遍历：

• 首先是序列化二叉树，广度优先遍历的遍历顺序是按照层级从上往下遍历（层序遍历），所以我们可以利用队列先进先出的特性，维持一个数组。先将根节点入队，再将左节点和右节点入队，递归即可。
• 之后是反序列化二叉树，我们可以从数组中取出第一个元素生成根节点，将根节点加入队列，循环队列，将根节点的左右子树分别加入队列，循环此操作，直至队列为空。其中队列中的节点用于后面遍历其左右子节点。

1）深度优先遍历：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function(root) {
    const result = []
    function traverseNode(node){
        if(node === null){
            result.push(null)
        }else{
            result.push(node.val)
            traverseNode(node.left)
            traverseNode(node.right)
        }
    }
    traverseNode(root)
    return result
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
    const len = data.length
    if(!len){
        return null
    }
    let i = 0
    function structure (){
        // 递归停止条件
        if(i >= len){
            return null
        }
        const val = data[i]
        i++
        if(val === null){
            return null
        }
        const node = new TreeNode(val)
        node.left = structure()
        node.right = structure()
        return node
    }
    return structure()
};

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */

复杂度分析：

• 时间复杂度：在序列化和反序列化函数中，我们只访问每个节点一次，因此时间复杂度为 O(n)，其中 n 是节点数，即树的大小。
• 空间复杂度：在序列化和反序列化函数中，我们递归会使用栈空间，故渐进空间复杂度为 O(n)。

2）广度优先遍历：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function(root) {
    if(!root){
        return []
    }
    const result = []
    const queue = []
    queue.push(root)

    let node ;
    while(queue.length){
        node = queue.shift()
        result.push(node ? node.val : null)
        if(node){
            queue.push(node.left)
            queue.push(node.right)
        }
    }
    return result
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
    const len = data.length
    if(!len){
        return null
    }
    const root = new TreeNode(data.shift())
    const queue = [root]
    while(queue.length){
        // 取出将要遍历的节点
        const node = queue.shift()
        if(!data.length){
            break
        }
        // 还原左节点
        const leftVal = data.shift()
        if(leftVal === null){
            node.left = null
        }else{
            node.left = new TreeNode(leftVal)
            queue.push(node.left)
        }
        if(!data.length){
            break
        }

        // 还原右节点
        const rightVal = data.shift()
        if(rightVal === null){
            node.right = null
        }else{
            node.right = new TreeNode(rightVal)
            queue.push(node.right)
        }
    }
    return root
};

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */

复杂度分析：

• 时间复杂度：在序列化和反序列化函数中，我们只访问每个节点一次，因此时间复杂度为 O(n)，其中 n 是节点数，即树的大小。
• 空间复杂度：在序列化和反序列化函数中，我们递归会使用栈空间，故渐进空间复杂度为 O(n)。

6. 经典题目：二叉搜索树的属性

（1）验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征：

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

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

首先使用DFS（深度优先遍历）递归遍历整棵树，检验每棵子树中是否都满足 左 < 根 < 右 这样的关系。

设定两个值：最大值和最小值分别为正无穷和负无穷，然后通过判断左孩子的值是否小于根节点，右孩子的值是否大于根节点来断定该二叉树是否是二叉搜索树。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * } 
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
   function dfs(root, minValue, maxValue){
       // 判断树为空的情况
       if(!root){
           return true
       }
       // 关键性的判断条件：左 < 根 < 右
       if(root.val <= minValue || root.val >= maxValue){
           return false
       }
       // 遍历左子树和右子树
       return dfs(root.left, minValue, root.val)&&dfs(root.right, root.val, maxValue)
   }
   // 对dfs遍历进行初始化
   return dfs(root, -Infinity, Infinity)
};

复杂度分析：

• 时间复杂度：O(n)：在递归调用的时候二叉树的每个节点最多被访问一次，因此时间复杂度为 O(n)。
• 空间复杂度：O(n)：递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，即二叉树的高度。最坏情况下二叉树为一条链，树的高度为 nn ，递归最深达到 nn 层，故最坏情况下空间复杂度为 O(n)。

【方法二】中序遍历 使用二叉树的中序遍历来判断。我们知道：二叉搜索树的中序遍历是有序的。所以，直接对二叉树进行中序遍历，将得出的数组进行遍历，判断这个数组是否是有序的。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
   const queue = []
   function dfs(root){
       if(!root){
           return true
       }
       if(root.left){
           dfs(root.left)
       }
       if(root){
           queue.push(root.val)
       }
       if(root.right){
           dfs(root.right)
       }
   }
   dfs(root)
   // 判断遍历的结果是否有序
   for(let i = 0; i<queue.length-1; i++){
       if(queue[i] >= queue[i+1]){
           return false
       }
   }
   return true
};

复杂度分析：

• 时间复杂度 : O(n)，其中 n为二叉树的节点个数。二叉树的每个节点最多被访问一次，因此时间复杂度为 O(n)。
• 空间复杂度 : O(n)，其中 n为二叉树的节点个数。栈最多存储 n个节点，因此需要额外的 O(n)的空间。

（2）二叉搜索树中第k小的元素

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。说明：你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 1

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 3

进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？

我们知道，二叉搜索树的左节点小于其父节点，右节点小于其右节点。这样二叉搜索树的中序遍历就是一个从小到大的有序序列。我们可以根据这个特性进行解答。

递归： 对二叉搜索树进行中序遍历，遍历的原则就是先遍历左子树，然后遍历根节点，最后遍历左子树。在遍历过程中，将遍历的结果不断存入数组中，当遍历到第k个元素的时候，就终止遍历。

迭代： 递归的方法也是利用的二叉搜索树的中序遍历：

1. 初始化一个栈暂存树的节点
2. 先遍历根节点，再遍历左子树，并保存在栈中
3. 遍历完左子树之后，将栈中的元素的出栈，这样顺序就反过来了，变成了先成遍历的根节点，再遍历的左子树
4. 在遍历的过程中，每遍历一次k就减一
5. 遍历完左子树之后再遍历右子树
6. 不断循环，直到k为0位置，返回当前的节点值。

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

// 递归的实现：
var kthSmallest = function(root, k) {
    const result = []
    function travel(node){
        if(result.length >= k) return 
        if(node.left){
            travel(node.left)
        }
        result.push(node.val)
        if(node.right){
            travel(node.right)
        }
    }
    travel(root)
    return result[k - 1]
};

// 迭代的实现：
let kthSmallest = function(root, k) {
    let stack = []
    let node = root
   
    while(node || stack.length) {
        // 遍历左子树
        while(node) {
            stack.push(node)
            node = node.left
        }
     
        node = stack.pop()
        if(--k === 0) {
            return node.val
        }
        node = node.right
    }
    return null
}

递归的复杂度分析：

• 时间复杂度：O(n)，其中n是二叉树的节点数，需要遍历了整个树。
• 空间复杂度：O(n)，用了一个数组存储中序序列。

迭代的复杂度分析：

• 时间复杂度：O(H+k)，其中 H 指的是树的高度，由于开始遍历之前，要先向下达到叶，当树是一个平衡树时：复杂度为 O(logN+k)。当树是一个不平衡树时：复杂度为 O(N+k)，此时所有的节点都在左子树。
• 空间复杂度：O(H+k)。当树是一个平衡树时：O(logN+k)。当树是一个非平衡树时：O(N+k)。

（3）二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第k大的节点。

示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 4

限制： 1 ≤ k ≤ 二叉搜索树元素个数

我们知道，二叉搜索树的中序遍历的结果是一个有大到小的数组，所以我们可以倒中序遍历，然后将第结果的第k大节点返回即可。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthLargest = function(root, k) {
    let res = []

    const dfs = (root) => {
        if(!root){
            return 
        }

        dfs(root.right)
        res.push(root.val)
        dfs(root.left)
    }
    dfs(root)

    return res[k - 1]
};

复杂度分析：

• 时间复杂度 O(n)，最差的情况下，也就是当树退化为链表时（全部为右子节点），无论 k 的值大小，递归深度都为 n ，占用 O(n) 时间；
• 空间复杂度 O(n)，最差的情况下，也就是当树退化为链表时（全部为右子节点），系统使用 O(n) 大小的栈空间。

（4）二叉搜索树的最小绝对差

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。示例：

输入：

   1
    \
     3
    /
   2

输出：
1

解释：
最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。

提示：树中至少有 2 个节点。

这道题目比较简单，先回忆一下二叉搜索树的特征：左子树的值始终小于父节点的值，右子树的值始终大于父节点的值。还有很重要的一点：在二叉搜索树的遍历中，中序遍历出来的结果是一个升序的数组。

那我们就可以进行中序遍历，并比较相邻的节点的值，始终保持结果是当前最小的值。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function(root) {
    let pre = null
    let min = Infinity
    
    let inOrderTravel = (root) => {
        if(root){
            inOrderTravel(root.left)
            if(pre){
                min = Math.abs(root.val - pre.val) < min ? Math.abs(root.val - pre.val) : min
            }
            pre = root
            inOrderTravel(root.right)
        }
    }
    inOrderTravel(root)
    return min
};

复杂度分析：

• 时间复杂度：O(n)，其中 n 为二叉搜索树节点数。每个节点在中序遍历中都会被访问一次且只会被访问一次，因此总时间复杂度为 O(n)。
• 空间复杂度：O(n)。递归函数的空间复杂度取决于递归的栈深度，而栈深度在二叉搜索树为一条链的情况下会达到 O(n) 级别。

（5）二叉搜索树中的众数

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。假定 BST 有如下定义：

• 结点左子树中所含结点的值小于等于当前结点的值
• 结点右子树中所含结点的值大于等于当前结点的值
• 左子树和右子树都是二叉搜索树

例如：给定 BST [1,null,2,2],

   1
    \
     2
    /
   2
返回[2].

提示：如果众数超过1个，不需考虑输出顺序 进阶： 你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

对于这道题目，我们可以对二叉树进行深度优先遍历，在遍历过程中，初始化一个max，用来保存当前元素出现的最大的次数，将二叉树值与对应的次数保存在一个map中，最后我们遍历一遍这个map，将所有次数与max相等的值都保存在res中即可。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */

var findMode = function(root) {
    let map = {}, max = 0, res = []

    const dfs = (root) => {
        if(!root){
            return []
        }
        map[root.val] ? map[root.val] += 1 : map[root.val] = 1;

        max = Math.max(max, map[root.val])
        dfs(root.left)
        dfs(root.right)
    }
    dfs(root)
    
    for(let key in map){
        if(max === map[key]){
            res.push(key)
        }
    }
    return res
};

复杂度分析：

• 时间复杂度：O(n)，其中n是这棵树的节点数量，我们需要遍历整棵树。
• 空间复杂度：O(n)，其中n是这棵树的节点数量，这里需要的是递归的栈空间的空间代价。

7. 经典题目：二叉搜索树的操作

（1）将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树_每个节点 _的左右两个子树的高度差的绝对值不超过 1。 示例： 给定有序数组: [-10,-3,0,5,9]，一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

二分递归实现： 将数组的值转化为一个高度平衡的二叉搜索树，我们只要找到中间的元素作为根节点，然后将中间元素的左边和右边分别二分，找出中间值作为子树的根节点，重复上述操作，直到遍历完整个数组为止即可。

• 当数组长度为奇数时，以中间值作为根节点，形成的平衡二叉搜索树的两侧差值为0。
• 当数组长度为偶数时，可以取中间两个元素的任意一个作为根节点的值，这样形成的平衡二叉树的两侧差值的绝对值为1。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
   if(!nums.length){
       return null
   }
   function bst(low, high){
       // 遍历结束条件
       if(low > high){
           return null
       }
       // 取出当前子序列的中间元素的索引值
       const mid = Math.floor(low+(high-low)/2)
       // 将中间元素的值作为当前子树的根节点
       const cur = new TreeNode(nums[mid])
       // 递归构建左子树
       cur.left = bst(low, mid-1)
       // 递归构建右子树
       cur.right = bst(mid+1, high)
       return cur
   }
   return bst(0, nums.length-1)
};

复杂度分析：

• 时间复杂度： O(log n)：通过二分查找的方式递归查询了树的所有子节点。查询花费 O(log n) 的时间。
• 空间复杂度： O(n)：每次递归都需要创建新的临时空间，空间复杂度 O(n)。

（2）二叉树搜索树中的搜索

给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。例如，

给定二叉搜索树:
    4
   / \
  2   7
 / \
1   3
和值: 2

你应该返回如下子树:

  2     
 / \   
1   3

在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */

// 迭代的实现：
var searchBST = function(root, val) {
   while(root){
       if(root.val === val){
           return root
       }else if(root.val <val){
           root = root.right
       }else{
           root = root.left
       }
   }
   return null
};

// 递归的实现：
var searchBST = function(root, val) {
   if(!root){
       return null
   }
   if(root.val === val){
       return root
   }else if(root.val < val){
       return searchBST(root.right, val)
   }else{
       return searchBST(root.left, val)
   }
};

迭代的复杂度分析：

• 时间复杂度：O(H)，其中 H 是树高。平均时间复杂度为 O(logN)，最坏时间复杂度为 O(N)。
• 空间复杂度：O(1)，恒定的额外空间。

递归的复杂度分析：

• 时间复杂度：O(H)，其中 H 是树高。平均时间复杂度为 O(logN)，最坏时间复杂度为 O(N)。
• 空间复杂度：O(H)，递归栈的深度为 H。平均情况下深度为 O(logN)，最坏情况下深度为 O(N)。

（3）二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。

例如，

给定二叉搜索树:
    4
   / \
  2   7
 / \
1   3
和 插入的值: 5

你可以返回这个二叉搜索树:

     4
   /   \
  2     7
 / \   /
1   3 5

或者这个树也是有效的:

     5
   /   \
  2     7
 / \   
1   3
     \
      4

二叉搜索树的性质：对于任意节点 root 而言，左子树（如果存在）上所有节点的值均小于 root.val，右子树（如果存在）上所有节点的值均大于 root.val，且它们都是二叉搜索树。

因此，当将val 插入到以root 为根的子树上时，根据 val 与 root.val 的大小关系，就可以确定要将val 插入到哪个子树中。

• 如果该子树不为空，则问题转化成了将 val 插入到对应子树上。
• 否则，在此处新建一个以 val 为值的节点，并链接到其父节点 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 {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
};

// 迭代的实现：
var insertIntoBST = function(root, val) {
    if(!root){
        return new TreeNode(val)
    }
    let cur = root
    while(cur){
        if(val > cur.val){
           if(!cur.right){
                cur.right = new TreeNode(val)
                return root
           }else{
               cur = cur.right
           }
        }else{
            if(!cur.left){
                cur.left = new TreeNode(val)
                return root
            }else{
                cur = cur.left
            }
        }
    }
    return root
};

迭代的复杂度分析：

• 时间复杂度：O(N)，其中 N 为树中节点数。最坏情况下，需要将值插入到树的最深的叶子结点上，而叶子节点最深为 O(N)。
• 空间复杂度：O(1)。我们只使用了常数大小的空间。

递归的复杂度分析：

• 时间复杂度：O(N)，其中 N 为树中节点数。最坏情况下，需要将值插入到树的最深的叶子结点上，而叶子节点最深为 O(N)。
• 空间复杂度：O(1)。我们只使用了常数大小的空间。

（4）将二叉搜索树变平衡

给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。如果有多种构造方法，请你返回任意一种。

示例：

输入：root = [1,null,2,null,3,null,4,null,null]
输出：[2,1,3,null,null,null,4]
解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。

提示：

• 树节点的数目在 1 到 10 之间。
• 树节点的值互不相同，且在 1 到 10 之间。

解题思路和上面的将一个有序数组转化为高度平衡的二叉搜索树问题类似。

我们知道，二叉搜索树的中序遍历是一个有序数组，那么就可以将题目给出的二叉搜索树进行中序遍历，将遍历得到的有序数组转化为平衡的二叉搜索树。其中后半部分和之前的解题思路完全一致。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var balanceBST = function(root) {
   // 初始化一个数组用来储存中序遍历的结果
   const nums = []
   // 对二叉搜索树进行中序遍历
   function inorder(root){
       if(!root){
           return 
       }
       inorder(root.left)
       nums.push(root.val)
       inorder(root.right)
   }
   // 将有序数组转化为高度平衡的二叉搜索树
   function buildAvl(low, high){
       if(low > high){
           return null
       }
       const mid = Math.floor(low+(high-low)/2)
       const cur = new TreeNode(nums[mid])
       cur.left = buildAvl(low, mid-1)
       cur.right = buildAvl(mid+1, high)
       return cur
   }
   inorder(root)
   return buildAvl(0, nums.length-1)
};

复杂度分析：

• 时间复杂度：由于每个节点最多被访问一次，因此总的时间复杂度为 O(N)，其中 N 为链表长度。
• 空间复杂度：虽然使用了递归，但是瓶颈不在栈空间，而是开辟的长度为 N 的 nums 数组，因此空间复杂度为 O(N)，其中 N 为树的节点总数。

（5）将有序链表转换为二叉搜索树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

由于数组是有序递增排列的，所以我们可以从数组的中间开始查找。利用递归+二分法来解决这个问题。具体实现思路如下：

• 找出数组的中间元素，作为二叉树的根节点的值
• 二叉树的左节点是0—mid-1的中间坐标对应的元素
• 二叉树的右节点是mid+1—arr.length-1的中间坐标对应元素
• 按照上面的规律进行地递归，直到数组元素遍历完

需要注意的是，最后的结果可能不唯一。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * 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 {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function(head) {
    const arr=[];
    while(head){
        arr.push(head.val)
        head = head.next
    }
    const resTree=function(left, right){
        if(left > right) return null
        const mid = Math.floor(left + (right - left)/2); 
        const res = new TreeNode(arr[mid]);
        res.left = resTree(left, mid-1);
        res.right = resTree(mid+1, right);
        return res
    }
    return resTree(0, arr.length-1) 
};

复杂度分析：

• 时间复杂度：O(n)，其中 n 是数组的长度。每个数字只访问一次。
• 空间复杂度：O(logn)，其中 n 是数组的长度。空间复杂度不考虑返回值，因此空间复杂度主要取决于递归栈的深度，递归栈的深度是 O(logn)。

（6）把二叉搜索树转换为累加树

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。例如：

输入: 原始二叉搜索树:
              5
            /   \
           2     13

输出: 转换为累加树:
             18
            /   \
          20     13

这也是一个简单题目，我们都知道二叉树的中序遍历结果是一个递增的数组。这里我们可以进行倒序进行中序遍历，这样遍历的出的数组就是递减的。

中序遍历的顺序是 **左子树→根节点→右子树。**所以可以先遍历右子树，再遍历根节点，最后遍历左子树。

这样的话，设置一个节点不断累加之前的值，那么在当前节点的值就会赋值成比他大的数的和。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var convertBST = function(root) {
    let sum = 0

    const inOrder = (root) => {
        if(!root){
            return 
        }
        if(root.right){
            inOrder(root.right)
        }
        sum += root.val
        root.val = sum
        if(root.left){
            inOrder(root.left)
        }
    }
    inOrder(root)
    return root
};

复杂度分析：

• 时间复杂度：O(n)，其中 n 是二叉搜索树的节点数。每一个节点恰好被遍历一次。
• 空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。

（7）修剪二叉搜索树

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

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

示例 1：

输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]

示例 2：

输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]

示例 3：

输入：root = [1], low = 1, high = 2
输出：[1]

示例 4：

输入：root = [1,null,2], low = 1, high = 3
输出：[1,null,2]

示例 5：

输入：root = [1,null,2], low = 2, high = 4
输出：[2]

提示：

• 树中节点数在范围 [1, 10] 内
• 0 <= Node.val <= 10
• 树中每个节点的值都是唯一的
• 题目数据保证输入是一棵有效的二叉搜索树
• 0 <= low <= high <= 10

对于这道题目，我们可以使用递归来实现。

• 如果当前结点小于下界，直接将修剪后的右子树替换当前节点并返回；
• 如果当前结点大于上界，直接将修剪后的左子树替换当前节点并返回；
• 如果当前节点在范围之内，就继续递归左右子树查找越界的节点。

/**
 * 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} low
 * @param {number} high
 * @return {TreeNode}
 */
var trimBST = function(root, low, high) {
    if(!root){
        return root
    }
    // 如果当前结点小于下界，直接将修剪后的右子树替换当前节点并返回
    if(root.val < low){
        return trimBST(root.right, low, high)
    }
    // 如果当前结点大于上界，直接将修剪后的左子树替换当前节点并返回
    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
};

复杂度分析：

• 时间复杂度：O(n)，其中 n 是给定的树节点数。我们最多访问每个节点一次。
• 空间复杂度：O(n)，这里虽然没有使用任何额外的内存，但是在最差情况下，递归调用的栈可能与节点数一样大。

（8）删除二叉搜索树中的节点

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

1. 首先找到需要删除的节点；
2. 如果找到了，删除它。

说明： 要求算法时间复杂度为 O(h)，h 为树的高度。 示例:

root = [5,3,6,2,4,null,7]
key = 3
    5
   / \
  3   6
 / \   \
2   4   7
给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
    5
   / \
  4   6
 /     \
2       7
另一个正确答案是 [5,2,6,null,4,null,7]。
    5
   / \
  2   6
   \   \
    4   7

我们知道，二叉搜索树的左子树总是比根节点小，右子树总是比根节点大，所以可以将根节点的值与要删除的 key 值对比，就知道要删除的值在哪个位置：

• 如果key 和根节点相等，那么就删除当前的根节点，退出递归；
• 如果key 比根节点值大，那么就要递归右子树去查找；
• 如果key 比根节点值小，那么就要递归左子树去查找；

当我们找到需要删除的节点时，会有以下四种情况：

• 待删除的节点的左右子节点均为空，那么就直接删除当前节点即可；
• 待删除的节点存在左子节点，而右子节点为空，那么就当前节点设置为左子节点的值；
• 待删除的节点存在右子节点，而左子节点为空，那么就当前节点设置为右子节点的值；
• 带删除的节点同时存在左子子节点，那么就要找到比当前节点小的最大节点（或者比当前节点大的最小节点）来替换掉当前的节点（下面代码中，我们是找的是比当前节点大的最小节点）；**

/**
 * 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){
        return root
    }

    if(root.val > key){
        root.left = deleteNode(root.left, key)
    }else if(root.val < key){
        root.right = deleteNode(root.right, key)
    }else{
        if(!root.left && !root.right){
            root = null
        }else if(root.left && !root.right){
            root = root.left
        }else if(!root.left && root.right){
            root = root.right
        }else if(root.left && root.right){
            let last = root.right
            while (last.left) {
                last = last.left
            }
            root.val = last.val
            root.right = deleteNode(root.right, last.val)
        }
    }
    return root

};

复杂度分析：

• 时间复杂度：O(logN)。在算法的执行过程中，我们一直在树上向左或向右移动。首先先用 O(H) 的时间找到要删除的节点，H指得是从根节点到要删除节点的高度。然后删除节点需要 O(H) 的时间，H指的是从要删除节点到替换节点的高度。由于 O(H+ H)=O(H)，H 指得是树的高度，若树是一个平衡树，则 H = logN。
• 空间复杂度：O(H)，递归时堆栈使用的空间，其中 H 是树的高度。

8. 经典题目：二叉树的公共祖先

（1）二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:

• 所有节点的值都是唯一的。
• p、q 为不同节点且均存在于给定的二叉树中。

对于二叉树的题目，经常用的就是递归遍历，这里我们也使用到了递归：

首先判断，如果树为空树或p、q中任意一节和根节点相等，那么p和q 的最近公共祖先节点就是根节点root。

如果树不为空树，并且p和q和根节点不相等，那么就递归遍历左右子树：

• 如果p和q节点在左右子树的最近公共祖先节点都存在，说明p和q分布在左右子树上，则它们的最近公共祖先节点就是根节点root。
• 如果只有一个子树递归有结果，说明p和q都在这个子树中，那么就返回该树的递归的结果。
• 如果两个子树递归结果都为null，说明p和q都不在这俩子树中，那么就返回根节点root。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    if(!root || root === p || root === q){
        return root
    }

    const left = lowestCommonAncestor(root.left, p, q)
    const right = lowestCommonAncestor(root.right, p, q)
    
    if(!left) return right
    if(!right) return left

    return root
};

复杂度分析：

• 时间复杂度: O(n)，其中 n 是二叉树节点的个数。这里遍历了二叉树的每个节点，所以时间复杂度为O(n)。
• 空间复杂度: O(n)，其中 n 是二叉树节点的个数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 n，所以空间复杂度为 O(n)。

（2）二叉搜索树的最近公共祖先

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

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

• 所有节点的值都是唯一的。
• p、q 为不同节点且均存在于给定的二叉搜索树中。

对于这道题目，我们可以使用递归或者迭代来实现。

1）递归实现： 对于二叉树搜索树：

• 如果 p.val 和 q.val 都比 root.val 小，则 p、q 肯定在 root 的左子树；
• 如果 p.val 和 q.val 都比 root.val 大，则 p、q 肯定在 root 的右子树；
• 如果 p.val 和 q.val 一个比 root.val 大，一个比 root.val 小，那说明这两个节点的最进公共祖先就是root；**

2）迭代实现： 我们可以使用一个 while 循环，当 root 为 null 时就结束循环：

• 如果 p.val 和 q.val 都比 root.val 小，则 p、q 肯定在 root 的左子树，root=root.left，遍历到 root 的左子节点。
• 如果 p.val 和 q.val 都比 root.val 大，则 p、q 肯定在 root 的右子树，root=root.right，遍历到 root 的右子节点。
• 其他情况，当前的 root 就是最近公共祖先，结束遍历，直接结束循环。

递归实现：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

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

迭代实现：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

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

迭代复杂度分析：

• 时间复杂度：O(n)，其中 n 是二叉搜索树的节点数。最坏的情况下，我们需要深度优先遍历整棵二叉树；
• 空间复杂度：O(1)，我们只需要常量空间来操作。

递归复杂度分析：

• 时间复杂度：O(n)，其中 n 是二叉搜索树的节点数。最坏的情况选，我们需要深度优先遍历整棵二叉树；
• 空间复杂度：O(n)，我们需要递归遍历这棵树，所以空间复杂度为O(n)；