二叉树的递归

# 二叉树的递归

# lc654. 最大二叉树中等

题目描述

给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的最大二叉树定义如下：

二叉树的根是数组 nums 中的最大元素。

左子树是通过数组中最大值左边部分递归构造出的最大二叉树。

右子树是通过数组中最大值右边部分递归构造出的最大二叉树。

返回有给定数组 nums 构建的最大二叉树。

示例 1：

输入：nums = [3,2,1,6,0,5]

输出：[6,3,5,null,2,0,null,null,1]

解释：递归调用如下所示：

\- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。

    \- [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。

        \- 空数组，无子节点。

        \- [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。

            \- 空数组，无子节点。

            \- 只有一个元素，所以子节点是一个值为 1 的节点。

    \- [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。

        \- 只有一个元素，所以子节点是一个值为 0 的节点。

        \- 空数组，无子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

示例 2：

输入：nums = [3,2,1]

输出：[3,null,2,null,1]

1
2
3

var constructMaximumBinaryTree = function(nums) {
  if(!nums.length) return null

  let max = Math.max(...nums)
  let root = new TreeNode(max)

  let leftArr = nums.slice(0, nums.indexOf(max))
  let rightArr = nums.slice(nums.indexOf(max) + 1)

  root.left = constructMaximumBinaryTree(leftArr)
  root.right = constructMaximumBinaryTree(rightArr)
  return root
};

1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度：O(n)，一共递归了 n 次。每次递归寻找根节点时，需要遍历当前索引范围内所有元素找出最大值。一般情况下，每次遍历的复杂度为 O(logn)，总复杂度为 O(nlogn)。最坏的情况下，数组 nums 有序，总的复杂度为 O(n)
空间复杂度：O(n)。递归调用深度为 n。平均情况下，长度为 n 的数组递归调用深度为 O(logn)。

# lc100. 相同的树简单

题目描述

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

输入：p = [1,2,3], q = [1,2,3]

输出：true

1
2
3

示例 2：

输入：p = [1,2], q = [1,null,2]

输出：false

1
2
3

示例 3：

输入：p = [1,2,1], q = [1,1,2]

输出：false

1
2
3

var isSameTree = function(p, q) {
  if(!p && !q) return true

  if(p === null || q === null) return false

  if(p.val !== q.val) return false

  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
};

1
2
3
4
5
6
7
8
9

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

# 572. 另一棵树的子树简单hot

题目描述

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1：

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

1
2

示例 2：

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

1
2

思路：和相同的树差不多思路

var isSubtree = function(root, subRoot) {
  if (root == null) return subRoot == null;
  var isSame = (p,q) => {
    if(!p || !q) return p === q
    return p.val === q.val && isSame(p.left,q.left) && isSame(p.right,q.right)
  }
  if(isSame(root,subRoot)) return true
  return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot)
};

1
2
3
4
5
6
7
8
9

时间复杂度：对于每一个 s 上的点，都需要做一次深度优先搜索来和 t 匹配，匹配一次的时间代价是 O(|t|)，那么总的时间代价就是 O(∣s∣×∣t∣)。

空间复杂度：假设 s 深度为 ds ,t 的深度为 dt，任意时刻栈空间的最大使用代价是 O(max(ds, dt))

# lc104. 二叉树的最大深度简单hot

题目描述

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

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

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

示例：

给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3

1
2
3
4
5
6
7
8
9

var maxDepth = function(root) {
  if(!root) return 0 
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
};
// 或者是这样
var maxDepth = function(root) {
    if(!root) return root;
    let ret = 1;
    function dfs(root, depth){
        if(!root.left && !root.right) ret = Math.max(ret, depth);
        if(root.left) dfs(root.left, depth+1);
        if(root.right) dfs(root.right, depth+1);
    }
    dfs(root, ret);
    return ret
};

// 迭代
var maxDepth = function(root) {
  if(!root) return 0
  const stack = [root]
  let depth = 0
  while(stack.length) {
    let len = stack.length
    while(len--) {
      let node = stack.shift()

      if(node.left) stack.push(node.left)
      if(node.right) stack.push(node.right)
    }
    depth++
  }
  return depth
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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

# lc110. 平衡二叉树简单hot

题目描述

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

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

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

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

1
2

示例 2：

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

1
2

示例 3：

输入：root = []

输出：true

1
2
3

法一：暴力自顶向下

思路：自顶向下，比较每个节点的左右子树的最大高度差，如果小于等于1，则为平衡二叉树

var isBalanced = function(root) {
    if(!root) return true

    return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right)
};

const depth = node => {
    if(!node) return -1
    return 1 + Math.max(depth(node.left), depth(node.right))
}

1
2
3
4
5
6
7
8
9
10

时间复杂度O(nlogn)

空间复杂度O(n)

法二：自底向上优化法

思路：先遍历到最底，然后依次向上返回子树的最大高度判断是否为平衡二叉树

遍历比较二叉树每个节点的左右子树深度：

比较左右子树的深度，若差值大于 1 则返回一个标记 -1 ，表示当前子树不平衡
左右子树有一个不是平衡的，或左右子树差值大于 1 ，则二叉树不平衡
若左右子树平衡，返回当前树的深度（左右子树的深度最大值 +1 ）

const isBalanced = (root) => {
    return balance(root) !== -1
}
const balance = node => {
    if(!node) return 0
    const left = balance(node.left)
    const right = balance(node.right)
    if(left === -1 || right === -1 || Math.abs(left - right) > 1) {
        return -1
    }
    return 1 + Math.max(left, right)
}

1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度O(n)

空间复杂度O(n)

# lc226. 翻转二叉树简单hot

题目描述

翻转一棵二叉树。

示例：

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13

递归

var invertTree = function(root) {
  if(!root) return null
  const left = invertTree(root.left)
  const right = invertTree(root.right)

  root.left = right
  root.right = left

  return root
};

1
2
3
4
5
6
7
8
9
10

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

迭代

var invertTree = function(root) {
  if(!root) return null
  const queue = [root]
  while(queue.length) {
    let node = queue.shift();
    [node.left, node.right] = [node.right, node.left]
    if(node.left) queue.push(node.left)
    if(node.right) queue.push(node.right)
  }
  return root
};

1
2
3
4
5
6
7
8
9
10
11

时间复杂度:O(n),需要遍历每个节点

空间复杂度:O(logn)

# lc617. 合并二叉树简单

题目描述

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

输入: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  

输出: 

合并后的树:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

思路就是保持root1不变，让root2加到root1上

var mergeTrees = function(root1, root2) {
  if(!root1 && root2) return root2

  if(root1 && !root2 || !root1 && !root2) return root1

  root1.val += root2.val

  root1.left = mergeTrees(root1.left, root2.left)
  root1.right = mergeTrees(root1.right, root2.right)

  return root1
};

1
2
3
4
5
6
7
8
9
10
11
12

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

# lc105. 从前序与中序序列构造二叉树中等hot

题目描述

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

1
2

示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

1
2

思路：

仔细分析前序遍历和中序遍历可以知道（以示例1为例）：

前序遍历的第一个元素一定是根节点，这里是3
找到根节点之后，根节点在中序遍历中把数组一分为二，即两个数组[9]和[15, 20, 7]，这两个数组分别是根节点3的左子树和右子树的中序遍历
前序遍历数组去掉根节点之后是[9,20,15,7]，而这个数组的第1项[9]（左子树的大小）和后3项[20, 15, 7]（右子树的大小）又分别是左子树和右子树的前序遍历到这里已经很明显了，用递归

/**
 * 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[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    if(preorder.length) {
        let node = new TreeNode(preorder.shift())
        let index = inorder.indexOf(node.val)

        let inleft = inorder.slice(0, index)
        let inright = inorder.slice(index + 1)

        let preleft = preorder.slice(0, index)
        let preright = preorder.slice(index)
        node.left = buildTree(preleft, inleft)
        node.right = buildTree(preright, inright)
        return node
    }
    return null

};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

# lc106. 从中序与后序序列构造二叉树中等hot

题目描述

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:

你可以假设树中没有重复的元素

例如，给出

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

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

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

1
2
3
4
5
6
7
8
9
10
11
12
13

var buildTree = function(inorder, postorder) {
  if(inorder.length) {
    let root = new TreeNode(postorder.pop())
    let index = inorder.indexOf(root.val)

    let inLeft = inorder.slice(0, index)
    let inRight = inorder.slice(index + 1)

    let postLeft = postorder.slice(0, index)
    let postRight = postorder.slice(index)

    root.left = buildTree(inLeft, postLeft)
    root.right = buildTree(inRight, postRight)

    return root
  }
  return null
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

# lc889. 从前序与后序序列构造二叉树中等hot

题目描述

返回与给定的前序和后序遍历匹配的任何二叉树。

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
2
3

var constructFromPrePost = function(preorder, postorder) {
  // pre = [[1],[2,4,5],[3,6,7]]
  // post = [[4,5,2],[6,7,3],[1]]
  if(preorder.length) {
    let root = new TreeNode(preorder.shift())
    // 剔除根节点先
    postorder.pop()
    // 先找到后序遍历中左子树的结尾处
    let postEnd = postorder.indexOf(preorder[0])
    // 找到先序遍历中左子树的结尾处
    // let preEnd = preorder.indexOf(postorder[postorder.length - 1])
    // 先序遍历的左子树就是 后序遍历左子树的长度
    let preLeft = preorder.splice(0, postEnd + 1)
    let preRight = preorder

    let postLeft = postorder.slice(0, postEnd + 1)
    let postRight = postorder.slice(postEnd + 1)
  
    root.left = constructFromPrePost(preLeft, postLeft)
    root.right = constructFromPrePost(preRight, postRight)
    return root 
  }
  return null
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# lc116. 填充每个节点的下一个右侧节点指针中等

题目描述

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

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

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

初始状态下，所有 next 指针都被设置为 NULL。

进阶：

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

示例：

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

输出：[1,#,2,3,#,4,5,6,7,#]

解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点
如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

1
2
3
4
5
6

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

1
2
3
4
5
6
7
8

时间复杂度：O(N)，其中n是二叉树的节点的数量，每个节点只访问一次。
空间复杂度：O(1)，不需要存储额外的节点

# lc117. 填充每个节点的下一个右侧节点指针 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 指针连接），'#' 表示每层的末尾。

1
2
3
4
5
6

var connect = function(root) {
  if(!root) return null
  const queue = [root]
  while(queue.length) {
    let queuelen = queue.length
    let last = null
    let idx = 0
    while(queuelen--) {
      let node = queue.shift()
      if(node.left) queue.push(node.left)
      if(node.right) queue.push(node.right)
      if(idx !== 0) last.next = node
      last = node
      idx++
    }
  }
  return root
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

# lc236. 二叉树最近公共祖先中等hot

题目描述

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

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

示例 1：

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

1
2
3

示例 2：

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

1
2
3

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

1
2

如果树为空树或 p 、 q 中任一节点为根节点，那么 p 、 q 的最近公共节点为根节点

如果不是，即二叉树不为空树，且 p 、 q 为非根节点，则递归遍历左右子树，获取左右子树的最近公共祖先，

如果 p 、 q 节点在左右子树的最近公共祖先都存在，说明 p 、 q 节点分布在左右子树的根节点上，此时二叉树的最近公共祖先为 root
若 p 、 q 节点在左子树最近公共祖先为空，那 p 、q 节点位于左子树上，最终二叉树的最近公共祖先为右子树上 p 、q 节点的最近公共祖先
若 p 、 q 节点在右子树最近公共祖先为空，同左子树 p 、 q 节点的最近公共祖先为空一样的判定逻辑
如果 p 、 q 节点在左右子树的最近公共祖先都为空，则返回 null

/**
 * 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 ===null || root === p || root === q) return root
    const left = lowestCommonAncestor(root.left, p, q)
    const right = lowestCommonAncestor(root.right, p, q)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

# lc235. 二叉搜索树的最近公共祖先简单

题目描述

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

例如，给定如下二叉搜索树: 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。

1
2
3
4
5

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4

输出: 2

解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

1
2
3
4
5

// 迭代
var lowestCommonAncestor = function(root, p, q) {
  while(root) {
    if(root.val < p.val && root.val < q.val) root = root.right
    else if(root.val > p.val && root.val > q.val) root = root.left
    else break
  }
  return root
};
// 时间复杂度：O(n)，其中 n 是二叉搜索树的节点数。最坏的情况下，我们需要深度优先遍历整棵二叉树；
// 空间复杂度：O(1)，我们只需要常量空间来操作

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 给定一个二叉树, 找到该树中两个指定节点间的最短距离hot

思路

const shortestDistance = function(root, p, q) {
    // 最近公共祖先
    let lowestCA = lowestCommonAncestor(root, p, q)
    // 分别求出公共祖先到两个节点的路经
    let pDis = [], qDis = []
    getPath(lowestCA, p, pDis)
    getPath(lowestCA, q, qDis)
    // 返回路径之和
    return (pDis.length + qDis.length)
}

// 最近公共祖先
const lowestCommonAncestor = function(root, p, q) {
    if(root === null || root === p || root === q) return root
    const left = lowestCommonAncestor(root.left, p, q)
    const right = lowestCommonAncestor(root.right, p, q)
    if(left === null) return right
    if(right === null) return left
    return root
}

const getPath = function(root, p, paths) {
    // 找到节点，返回 true
    if(root === p) return true
    // 当前节点加入路径中
    paths.push(root)
    let hasFound = false
    // 先找左子树
    if (root.left !== null)
        hasFound = getPath(root.left, p, paths)
    // 左子树没有找到，再找右子树
    if (!hasFound && root.right !== null)
        hasFound = getPath(root.right, p, paths)
    // 没有找到，说明不在这个节点下面，则弹出
    if (!hasFound)
        paths.pop()
    return hasFound
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

# lc112. 路径之和简单hot

题目描述

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

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

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22

输出：true

1
2
3

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false

1
2

示例 3：

输入：root = [1,2], targetSum = 0
输出：false

1
2

思路

只需要遍历整棵树

如果当前节点不是叶子节点，递归它的所有子节点，传递的参数就是 sum 减去当前的节点值；
如果当前节点是叶子节点，判断参数 sum 是否等于当前节点值，如果相等就返回 true，否则返回 false。

/**
 * 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} targetSum
 * @return {boolean}
 */
var hasPathSum = function(root, targetSum) {
    // 根节点为空
    if(!root) return false

    // 叶节点 sum等于叶节点的值
    if(root.left === null && root.right === null) return root.val === targetSum

    targetSum = targetSum - root.val
    // 总和减去当前值 然后递归
    return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum)
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

时间复杂度:O(n)

空间复杂度:O(h)

bfs

var hasPathSum = function(root, targetSum) {
  if (!root) return false
  const stack = [[root, root.val]]
  while(stack.length > 0) {
    const [node, pathSum] = stack.pop()
    const { left: lc, right: rc } = node
    if (pathSum === sum && !rc && !lc) return true
    if (rc) stack.push([rc, pathSum + rc.val]) // 前序遍历，需要先将右节点入栈，这样出栈时为左节点先出栈
    if (lc) stack.push([lc, pathSum + lc.val])
  }
  return false
};

1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度:O(n)

空间复杂度:O(n)

# lc113. 路径总和 II

题目描述

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

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

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

1
2

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：[]

1
2

示例 3：

输入：root = [1,2], targetSum = 0
输出：[]

1
2

思路：回溯

var pathSum = function(root, targetSum) {
  if (!root) return []
  const res = []
  const dfs = (node, currentSum, path) => {
    if(!node) return 
    currentSum += node.val
    path.push(node.val)

    if(!node.left && !node.right && currentSum === targetSum){
      res.push([...path])
    } 

    dfs(node.left, currentSum, path)
    dfs(node.right, currentSum, path)

    path.pop()
  }
  dfs(root, 0, [])

  return res
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度：O(N^2)，其中 N 是树的节点数。

在最坏情况下，树的上半部分为链状，下半部分为完全二叉树，并且从根节点到每一个叶子节点的路径都符合题目要求。此时，路径的数目为 O(N)，并且每一条路径的节点个数也为 O(N)，因此要将这些路径全部添加进答案中，时间复杂度为 O(N^2)

空间复杂度：O(N)，其中 N 是树的节点数。空间复杂度主要取决于栈空间的开销，栈中的元素个数不会超过树的节点数。

# lc101. 对称二叉树简单hot

题目描述

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
       1
      / \
     2   2 
    / \ / \
   3  4 4  3

1
2
3
4
5
6

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
       1
      / \ 
     2   2
      \    \ 
       3    3

1
2
3
4
5
6

法一：递归

比较左右子树的根节点是否相等
比较左子树的右节点是否等于右子树的左节点
比较右子树的左节点是否等于左子树的右节点

边界

左右子树为null则返回true
左右子树有一个为null返回false

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if(!root) return true

    const isEqual = (left, right) => {
        if(!left &&!right) return true
        if(!left ||!right) return false

        return left.val === right.val && isEqual(left.left, right.right) && isEqual(left.right, right.left)
    }

    return isEqual(root.left, root.right)
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

时间复杂度：O(n)

空间复杂度：O(n)

法二：迭代

利用调用栈的方法
每次进栈两个左右子树(root.left, root.right)
如果这两个左右子树的值相等的话
依次进栈左子树的right 右子树的left
进栈右子树的left 左子树的right
反复

var isSymmetric = function(root) {
    if(!root) return true
    const stack = [root.left, root.right]

    while(stack.length) {
        let right = stack.pop()
        let left = stack.pop()

        if(left && right) {
            if(left.val !== right.val) return false
            stack.push(left.left, right.right)
            stack.push(right.left, left.right)
        }
        else if(left || right){
            return false
        }
        
    }
    return true
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度：O(n)

空间复杂度：O(n)

# lc96. 不同的二叉搜索树中等

题目描述

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5

1
2

示例 2：

输入：n = 1
输出：1

1
2

思路

有n个节点，有多少种BST，和节点的value没有关系。也就是说1，2，3和4，5，6分别都是可以构成5种不同的BST。我们可以从1-n中，任意选择一个作为root，从中序遍历的角度，把root看成是中间节点。

如果将root定为m，那么以m为root，所构成的BST数量为：f(m-1)*f(n-m),从平凡角度出发，将f(n)的值定义成结果，结果就是所有节点作为root构成BST的数量和。有：

不同的BST02.png

dp[0]初始化为1，本身不具备意义，只保证递归式的不变性。外层循环控制数据规模递增1->n，内层循环将m的所有取值相加

var numTrees = function(n) {
  const dp = new Array(n + 1).fill(0)
  dp[0] = 1
  for(let i = 1; i <= n; i++) {
    for(let j = 1; j <= i; j++) {
      dp[i] += dp[j - 1] * dp[i - j]
    }
  }
  return dp[n]
};

1
2
3
4
5
6
7
8
9
10

时间复杂度 : O(n^2)，其中n 表示二叉搜索树的节点个数。G(n) 函数一共有 n 个值需要求解，每次求解需要 O(n) 的时间复杂度，因此总时间复杂度为 O(n^2)

空间复杂度 : O(n)。我们需要 O(n) 的空间存储 G数组

# lc108. 将有序数组转换成二叉搜索树简单

题目描述

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

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

示例 1：

输入：nums = [-10,-3,0,5,9]

输出：[0,-3,9,-10,null,5]

解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案

1
2
3
4
5

示例 2：

输入：nums = [1,3]

输出：[3,1]

解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。

1
2
3
4
5

使用二分法建立树

var sortedArrayToBST = function(nums) {
  if(!nums.length) return null

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

# lc1382. 将二叉搜索树变平衡中等

题目描述

给你一棵二叉搜索树，请你返回一棵平衡后的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 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
2
3
4
5

思路就是用中序遍历把二叉搜索树变成一个有序数组然后重建二叉树

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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

# lc109. 有序链表转换为二叉搜索树中等

题目描述

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

示例:

给定的有序链表：

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

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

      0
     / \
   -3   9
   /   /
 -10  5

1
2
3
4
5
6
7
8
9
10
11

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

# lc538. 把二叉搜索树转换为累加树中等

题目描述

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

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键小于节点键的节点。

节点的右子树仅包含键大于节点键的节点。

左右子树也必须是二叉搜索树。

示例 1：

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]

输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

1
2
3

示例 2：

输入：root = [0,null,1]

输出：[1,null,1]

1
2
3

示例 3：

输入：root = [1,0,2]

输出：[3,3,2]

1
2
3

示例 4：

输入：root = [3,2,4,1]

输出：[7,9,4,10]

1
2
3

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

# lc669. 修剪二叉搜索树中等

题目描述

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

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

示例 1：

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

输出：[1,null,2]

1
2
3

示例 2：

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

输出：[3,2,null,1]

1
2
3

示例 3：

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

输出：[1]

1
2
3

示例 4：

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

输出：[1,null,2]

1
2
3

示例 5：

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

输出：[2]

1
2
3

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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

# lc450. 删除二叉搜索树中的节点中等

题目描述

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

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；

如果找到了，删除它。

示例 1:

输入：root = [5,3,6,2,4,null,7], key = 3

输出：[5,4,6,2,null,null,7]

解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

另一个正确答案是 [5,2,6,null,4,null,7]

1
2
3
4
5
6
7
8
9

示例 2:

输入: root = [5,3,6,2,4,null,7], key = 0

输出: [5,3,6,2,4,null,7]

解释: 二叉树不包含值为 0 的节点

1
2
3
4
5

示例 3:

输入: root = [], key = 0

输出: []

1
2
3

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

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

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

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

var deleteNode = function(root, key) {
  if(!root) return root

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

# 剑指 Offer 36. 二叉搜索树与双向链表中等hot

题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

为了让您更好地理解问题，以下面的二叉搜索树为例：

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

思路：bfs

因为是二叉搜索树，中序遍历的结果顺序为升序；假设我们先后遍历的两个结点为a和b，那么根据题意，我们需要将a的右节点指向b，b的左节点指向a；因为中序遍历是按左中右顺序，a一定在b的左侧，我们修改a的右孩子和b的左孩子，不影响后面的遍历过程；同时需要是环形链表，我们记录首尾节点，在最后进行处理即可；

var treeToDoublyList = function(root) {
  // 树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
  // l,m,r -> r,m,l
  if (root === null) return root;
  let head = null, tail = null;
  let pre = null;
  let stk = [root];
  while (stk.length) {
    let cur = stk.pop();
    if (cur === null) {
      cur = stk.pop();
      if (head === null) {
        head = cur;
        tail = cur;
        pre = cur;
        continue;
      }
      tail = cur;
      tail.left = pre;
      pre.right = tail;
      pre = cur;
      continue;
    }
    if (cur.right !== null) stk.push(cur.right);
    stk.push(cur, null);
    if (cur.left !== null) stk.push(cur.left);
  }
  head.left = tail;
  tail.right = head;
  return head;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

时间复杂度：O(n)

空间复杂度：O(n)

思路：dfs

中序遍历深度优先搜索dfs，我们用pre记录前一个节点，head记录头结点判断pre节点是否存在若pre节点不存在时，说明是第一个节点，head指向当前node 若pre节点存在时，说明不是第一个节点，我们可以将前一个节点的后继节点指向当前node 因为是从小到大遍历的，所以知道当前节点的前一个节点，因此当当前节点node的前驱节点指向pre

在下次循环前，将pre指向当前node 遍历完整个二叉树，我们需要将首尾节点进行串联，此时head指向头结点，pre指向尾节点，因此将尾结点pre的后继节点指向头结点head，pre.right = head 将头结点head的前驱节点指向尾结点pre，head.left = pre

var treeToDoublyList = function(root) {
  if (root == null) return root
  let head, pre
  dfs(root)
  head.left = pre
  pre.right = head
  return head

  function dfs(node) {
    if (!node) return
    dfs(node.left)

    if (!pre) head = node
    else pre.right = node
    node.left = pre
    pre = node

    dfs(node.right)
  }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

上次更新: 2022/03/20, 19:40:28

← 二叉树的深度优先二叉搜索树→