跟着卡哥学算法Day 14：二叉树常见题目2

226.翻转二叉树 🌟#

题目描述#

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

解题思路#

翻转：将每个节点的左右子节点进行交换

通常可以用前序或后序，因为可以在访问中节点的时候直接交换左右子树
中序遍历，先处理完左子树之后交换左右，可能会导致原来的左子树被处理两次

如：

1
//       1
2
//      / \
3
//     2   3
4
//    / \
5
//   4   5

前序遍历：
1. 处理中间节点 1（交换 2 和 3）
2. 再处理左节点（此时为 3）
3. 最后右节点（此时为 2）
中序遍历
1. 处理左子树（节点 4）
2. 回到中间节点 2，交换左右子树（4 和 5 互换位置）
3. 处理新的右子树（原左子树 4），导致节点 4 被重复处理，而节点 5 未被处理

递归#

1
// 前序遍历
2
function invertTree(root) {
3
  if (!root) return null
4
  ;[root.right, root.left] = [root.left, root.right]
5
  invertTree(root.left)
6
  invertTree(root.right)
7

8
  return root
9
}

迭代#

1
// 统一模板的前序遍历
2
function invertTree(root) {
3
  if (!root) return root
4
  const invertNode = (root, left, right) => {
5
    const temp = right
6
    right = left
7
    left = temp
8
    root.left = left
9
    root.right = right
10
  }
11

12
  const stack = [root]
13

14
  while (stack.length) {
15
    let node = stack.pop()
16
    if (!node) {
17
      node = stack.pop()
18
      invertNode(node, node.left, node.right)
19
    } else {
20
      node.right && stack.push(node.right)
21
      node.left && stack.push(node.left)
22
      stack.push(node)
23
      stack.push(null)
24
    }
25
  }
26
  return root
27
}

层序#

1
function invertTree(root) {
2
  const invertNode = (root, left, right) => {
3
    const temp = right
4
    right = left
5
    left = temp
6
    root.left = left
7
    root.right = right
8
  }
9
  if (!root) return root
10
  const queue = [root]
11
  while (queue.length) {
12
    let node = queue.shift()
13
    invertNode(node, node.left, node.right)
14
    node.left && queue.push(node.left)
15
    node.right && queue.push(node.right)
16
  }
17
  return root
18
}

101. 对称二叉树 🌟#

力扣链接 🌟

题目描述#

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

解题思路#

必须使用后序遍历：需要先获取左右子树的信息，才能确定当前节点是否满足对称条件
如果前序遍历：先处理根节点，此时左右节点都还没有处理，那么就无法判断是否对称

递归三部曲：

确定递归函数的参数和返回值
- 参数：比较左右子树是不是对称树，所以参数自然是左子树节点和右子树节点
- 返回值：bool

确定终止条件

比较两个节点数值是否相同，一共三种情况：

左右同时为 null，对称
一个为 null，另一个不为 null，不对称
都不为 null，值不想等，不对称

1
// 同时为空，对称
2
if (!left && !right) return true
3
// 一个为空，另一个非空，不对称
4
if (!left || !right) return false
5
// 值不相等，直接返回 false
6
if (left.val !== right.val) return false

确定单层递归逻辑
- 比较左节点的左孩子和右节点的右孩子 compare(left.left, right.right)
- 以及左节点的右孩子和右节点的左孩子 compare(left.right, right.left)
- 同时为 true，则相等

代码#

递归#

1
function isSymmetric(root) {
2
  if (!root) return true
3

4
  const compare = (left, right) => {
5
    // 左右都为null
6
    if (!left && !right) return true
7
    // 左右一个为null
8
    if (!left || !right) return false
9
    // 左右都不为null，值不想等
10
    if (left.val !== right.val) return false
11

12
    return compare(left.left, right.right) && compare(left.right, right.left)
13
  }
14

15
  return compare(root.left, root.right)
16
}

迭代#

1
function isSymmetric(root) {
2
  if (!root) return true
3
  const stack = []
4
  stack.push(root.left)
5
  stack.push(root.right)
6

7
  while (stack.length) {
8
    let left = stack.pop()
9
    let right = stack.pop()
10
    if (!left && !right) continue
11
    if (!left || !right || left.val !== right.val) {
12
      return false
13
    }
14

15
    stack.push(left.left)
16
    stack.push(right.right)
17
    stack.push(left.right)
18
    stack.push(right.left)
19
  }
20

21
  return true
22
}

二叉树的最大深度#

力扣链接

题目描述#

给定一个二叉树 root ，返回其最大深度。

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

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

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

1
//       3
2
//      / \
3
//     9  20
4
//       / \
5
//      15 7

返回它的最大深度 3

解题思路#

二叉树节点深度：从根节点到该节点的路径长度
二叉树节点高度：指从该节点到叶子节点的最长路径

遍历方式#

二叉树节点深度

使用前序遍历 中 -> 左 -> 右，节点的深度由其父节点的深度决定（深度 = 父节点深度 + 1）。在遍历时，需要先访问当前节点（记录其深度），再递归处理子节点。
二叉树节点高度

使用后序遍历 左 -> 右 -> 中，节点的高度取决于其左右子树的高度。必须先知道左右子树的高度，才能计算当前节点的高度（当前高度 = max(左子树高度, 右子树高度) + 1）。

根节点的高度就是二叉树的最大深度

递归三部曲#

确定递归函数的参数和返回值
- 参数：当前节点
- 返回值：当前树的高度
确定终止条件
- 节点为 null ，返回高度为 0
确定单层递归逻辑
- 求左子树高度
- 求右子树高度
- 返回左右子树高度的较大值 + 1

代码#

递归#

1
function maxDepth(root) {
2
  if (!root) return 0
3
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
4
}

迭代#

1
function maxDepth(root) {
2
  if (!root) return 0
3
  let queue = [root]
4
  let depth = 0
5
  while (queue.length) {
6
    depth++
7
    let len = queue.length
8
    while (len) {
9
      const node = queue.shift()
10
      node.left && queue.push(node.left)
11
      node.right && queue.push(node.right)
12
      len--
13
    }
14
  }
15
  return depth
16
}

二叉树的最小深度#

力扣链接

题目描述#

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

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

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

示例:

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

1
//       3
2
//      / \
3
//     9  20
4
//       / \
5
//      15 7

返回它的最大深度 2

解题思路#

二叉树节点深度：指从根节点到该节点的最长简单路径边的节点数
二叉树节点高度：指从该节点到叶子节点的最长简单路径边的节点数

根节点的高度就是二叉树的最大深度

递归三部曲#

确定递归函数的参数和返回值
- 参数：当前节点
- 返回值：当前树的高度
确定终止条件
- 节点为 null ，返回高度为 0
确定单层递归逻辑
- 求左子树高度
- 求右子树高度
- 左子树为空，右子树不为空，返回右子树高度 + 1
- 右子树为空，左子树不为空，返回左子树高度 + 1
- 左右子树都不为空，返回左右子树高度的较小值 + 1

代码#

递归#

1
function minDepth(root) {
2
  if (!root) return 0
3
  // 到叶子节点 返回 1
4
  if (!root.left && !root.right) return 1
5
  // 只有右节点时 递归右节点
6
  if (!root.left) return 1 + minDepth(root.right)
7
  // 只有左节点时 递归左节点
8
  if (!root.right) return 1 + minDepth(root.left)
9
  return Math.min(minDepth(root.left), minDepth(root.right)) + 1
10
}

迭代#

1
function minDepth(root) {
2
  if (root === null) return 0
3
  let queue = [root]
4
  let depth = 0
5
  while (queue.length) {
6
    let length = queue.length
7
    depth++
8
    while (length) {
9
      const node = queue.shift()
10

11
      if (!node.left && !node.right) {
12
        return depth
13
      }
14

15
      node.left && queue.push(node.left)
16
      node.right && queue.push(node.right)
17
      length--
18
    }
19
  }
20
  return depth
21
}

音乐

音乐

226.翻转二叉树 🌟#

题目描述#

解题思路#

递归#

迭代#

层序#

101. 对称二叉树 🌟#

题目描述#

解题思路#

代码#

递归#

迭代#

二叉树的最大深度#

题目描述#

解题思路#

遍历方式#

递归三部曲#

代码#

递归#

迭代#

二叉树的最小深度#

题目描述#

解题思路#

递归三部曲#

代码#

递归#

迭代#

音乐

文章目录