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

110.平衡二叉树 🌟🌟#

题目描述#

给定一个二叉树，在q树的最后一行找到最左边的值。

示例 1:

给定二叉树 [2, 1, 3]

1
//       2
2
//      / \
3
//     1  3

输出：1

示例 2:

给定二叉树 [1, 2, 3, 4, 5, 6, 7]

1
//       1
2
//      / \
3
//     2  3
4
//    /  / \
5
//   4  5  6
6
//      /
7
//     7

输出：7

解题思路#

关键：在树的最底层找到最左边的值
最底层：二叉树最大深度的一层
最左边：该层中最靠左边的节点

递归#

递归三部曲：

明确递归函数的参数和返回值
- 参数 1：当前传入节点
- 参数 2：当前节点的深度
- 返回值：无
明确终止条件
- 遇到叶子节点 !root.left && !root.right，当前深度与最大深度比较，大于最大深度，则更新最大深度 maxDepth 和最大深度最左边的值 result
确定单层递归逻辑
- 分别计算左子树和右子树最大深度

1
function findBottomLeftValue(root) {
2
  let result = 0
3
  let maxDepth = 0
4

5
  const traverse = (node, depth) => {
6
    if (!node) return
7

8
    if (!node.left && !node.right) {
9
      if (depth > maxDepth) {
10
        maxDepth = depth
11
        result = node.val
12
      }
13
    }
14

15
    traverse(node.left, depth + 1)
16
    traverse(node.right, depth + 1)
17
  }
18

19
  traverse(root, 0)
20
}

迭代#

求最后一行第一个节点的数值

1
function findBottomLeftValue(root) {
2
  if (!root) return null
3
  let result = 0
4
  const queue = [root]
5

6
  while (queue.length) {
7
    const length = queue.length
8
    for (let i = 0; i < length; i++) {
9
      const cur = queue.shift()
10
      if (i === 0) result = cur.val
11
      cur.left && queue.push(cur.left)
12
      cur.right && queue.push(cur.right)
13
    }
14
  }
15

16
  return result
17
}

112. 路径总和 🌟#

力扣链接 🌟

题目描述#

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

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

示例: 给定如下二叉树，以及目标和 sum = 22，

1
//       5
2
//      / \
3
//     4  8
4
//    /  / \
5
//   11 13 4
6
//   /\     \
7
//  7 2     1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

解题思路#

递归#

递归三部曲：

确定递归函数的参数和返回值
- 参数 1：根节点
- 参数 2：计数器，用来计算二叉树的一条边之和是否等于目标值
- 返回值：bool
确定终止条件

从根节点开始目标值递减，直到叶子节点时判断是否为 0
```
1
if (!node.left && !node.right) {
2
  return count === 0
3
}
```
确定单层递归逻辑
- 递归左右子节点，传递剩余和 count - cur.left.val count - cur.right.val

1
function hasPathSum(root, count) {
2
  if (!root) return false
3

4
  if (!root.left && !root.right) {
5
    return count === root.val
6
  }
7

8
  return (
9
    hasPathSum(root.left, count - root.val) ||
10
    hasPathSum(root.right, count - root.val)
11
  )
12
}

迭代#

与递归不同，迭代记录当前路径和，再与目标值进行比较

步骤：

初始化栈：根节点和初始和存入栈
遍历栈：弹出节点及当前和，若为叶子且和等于目标值，返回 true
压入子节点：将左右子节点及更新后的和压入栈

1
function hasPathSum(root, count) {
2
  if (!root) return false
3

4
  const stack = [[root, root.val]]
5
  while (stack.length) {
6
    const [node, currentCount] = stack.pop()
7

8
    if (!node.left && !node.right && count === currentCount) {
9
      return true
10
    }
11

12
    node.left && stack.push([node.left, currentCount + node.left.val])
13
    node.right && stack.push([node.right, currentCount + node.right.val])
14
  }
15

16
  return false
17
}

113. 路径总和 II 🌟🌟#

力扣链接 🌟🌟

题目描述#

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

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

示例: 给定如下二叉树，以及目标和 sum = 22，

1
//       5
2
//      / \
3
//     4  8
4
//    /  / \
5
//   11 13 4
6
//   /\   / \
7
//  7 2   5 1

输出：[[5,4,11,2],[5,8,4,5]]

解题思路#

递归#

递归三部曲：

确定递归函数的参数和返回值
- 参数 1：根节点
- 参数 2：计数器，用来计算二叉树的一条边之和是否等于目标值
- 返回值：void
确定终止条件

从根节点开始目标值递减，当前节点是叶子节点且剩余和等于节点值 → 保存路径。
```
1
if (!node.left && !node.right && node.val === count) {
2
}
```
确定单层递归逻辑
- 递归左右子节点，传递剩余和 count - cur.val count - cur.val
- 递归结束后回溯（从路径中移除当前节点）

1
function pathSum(root, count) {
2
  if (!root) return
3
  const result = []
4
  const currentPath = []
5

6
  const traverse = (node, targetNum) => {
7
    if (!node) return
8

9
    currentPath.push(node.val)
10
    if (!node.left && !node.right && node.val === targetNum) {
11
      result.push([...currentPath]) // 深拷贝 避免后续影响
12
    }
13

14
    node.left && traverse(node.left, targetNum - node.left.val)
15
    node.right && traverse(node.right, targetNum - node.right.val)
16
    currentPath.pop() // 回溯：移除当前节点
17
  }
18

19
  traverse(root, count)
20

21
  return result
22
}

迭代#

用栈存储节点、剩余和及当前路径。遍历时更新路径和剩余和，遇到叶子节点且满足条件则保存路径。

步骤：

初始化栈：根节点、目标和、空路径入栈
遍历栈：弹出节点，若为叶子且剩余和等于节点值，保存路径
压入子节点：将左右子节点、更新后的剩余和及新路径压入栈

1
function pathSum(root, targetSum) {
2
  if (!root) return []
3

4
  const result = []
5
  const stack = [[root, targetSum, []]]
6
  while (stack.length) {
7
    const [node, currentCount, path] = stack.pop()
8

9
    const currentPath = [...path, node.val]
10
    if (!node.left && !node.right && node.val === currentCount) {
11
      result.push(currentPath)
12
    }
13

14
    node.left && stack.push([node.left, currentCount - node.val, currentPath])
15
    node.right && stack.push([node.right, currentCount - node.val, currentPath])
16
  }
17

18
  return result
19
}

106. 从中序与后序遍历序列构造二叉树 🌟🌟#

力扣链接 🌟🌟

题目描述#

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

注意: 你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树：

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

解题思路#

构造二叉树流程：

如果后序数组大小为零，说明时空节点，停止
如果不为空，取后序数组最后一个元素就是根节点（后序确定根节点）
找到后序数组最后一个元素在中序数组中的位置，作为切割点（中序分割左右子树）
切割中序数组，中序左数组作为左子树，中序右数组作为右子树
根据中序左数组长度
切割后序数组，切成后序左数组作为左子树，和后序右数组作为右子树
递归 1 - 5 步骤

递归三部曲#

确定递归函数的参数和返回值
- 参数 1：中序数组
- 参数 2：后序数组
- 返回值：根节点
确定终止条件
- 数组长度为空时，返回 null
确定单层递归逻辑
- 获取后序数组最后一个元素，作为根节点 const rootVal = postorder.pop()
- 获取中序数组中根节点的 index const rootIndex = inorder.indexOf(rootVal)
- 以根节点创建树 const root = new TreeNode(rootVal)
- 递归构造左子树 root.left = buildTree(inorder.slice(0, rootIndex), postorder.slice(0, rootIndex))
- 递归构造右子树 root.right = buildTree(inorder.slice(rootIndex + 1), postorder.slice(rootIndex))

代码#

1
function buildTree(inorder, postorder) {
2
  if (inorder.length === 0) return null
3

4
  const rootVal = postorder.pop()
5
  const rootIndex = inorder.indexOf(rootVal)
6
  const root = new TreeNode(rootVal)
7

8
  root.left = buildTree(
9
    inorder.slice(0, rootIndex),
10
    postorder.slice(0, rootIndex)
11
  )
12
  root.right = buildTree(
13
    inorder.slice(rootIndex + 1),
14
    postorder.slice(rootIndex)
15
  )
16

17
  return root
18
}

105. 从前序与中序遍历序列构造二叉树 🌟🌟#

力扣链接 🌟🌟

题目描述#

给给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

解题思路#

代码#

1
var buildTree = function (preorder, inorder) {
2
  if (!preorder.length) return null
3
  const rootVal = preorder.shift()
4
  const rootIndex = inorder.indexOf(rootVal)
5
  const root = new TreeNode(rootVal)
6

7
  root.left = buildTree(
8
    preorder.slice(0, rootIndex),
9
    inorder.slice(0, rootIndex)
10
  )
11
  root.right = buildTree(
12
    preorder.slice(rootIndex),
13
    inorder.slice(rootIndex + 1)
14
  )
15
  return root
16
}

音乐

音乐

110.平衡二叉树 🌟🌟#

题目描述#

解题思路#

递归#

迭代#

112. 路径总和 🌟#

题目描述#

解题思路#

递归#

迭代#

113. 路径总和 II 🌟🌟#

题目描述#

解题思路#

递归#

迭代#

106. 从中序与后序遍历序列构造二叉树 🌟🌟#

题目描述#

解题思路#

递归三部曲#

代码#

105. 从前序与中序遍历序列构造二叉树 🌟🌟#

题目描述#

解题思路#

代码#

音乐

文章目录