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

110.平衡二叉树 🌟#

题目描述#

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

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

示例 1:

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

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

返回 true

解题思路#

递归#

递归三部曲：

明确递归函数的参数和返回值
- 参数：当前传入节点
- 返回值：当前节点作为根节点的树高度
明确终止条件
- 节点为 null，返回 0
- 左右子树不平衡，直接返回
确定单层递归逻辑
- 计算左子树高度和右子树高度
- 如果已经返回 -1，则子树不平衡，直接返回 -1
- 如果左右子树平衡，计算左右子树高度差是否大于 1，如果大于 1 则不平衡，返回-1
- 继续返回当前子树的高度

1
function isBalanced(root) {
2
  const getDepth = (root) => {
3
    if (!node) return 0
4
    let leftDepth = getDepth(root.left)
5
    let rightDepth = getDepth(root.right)
6
    if (leftDepth === -1 || rightDepth === -1) return -1
7

8
    if (Math.abs(leftDepth - rightDepth) > 1) return -1
9

10
    return Math.max(leftDepth, rightDepth) + 1
11
  }
12

13
  return getDepth(root) !== -1
14
}

257. 二叉树的所有路径 🌟#

力扣链接 🌟

题目描述#

给定一个二叉树，返回所有从根节点到叶子节点的路径。

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

示例：

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

输出：['1 -> 2 -> 5','1 -> 3']

解题思路#

必须使用前序遍历：获取从根节点到叶子节点的路径

递归三部曲：

确定递归函数的参数和返回值
- 参数 1：根节点
- 参数 2：要递归记录每一条路径的 path，所以需要传入 path
- 返回值：不需要
确定终止条件

路径是从根到叶子节点，所以遇到叶子节点时，就需要记录
```
1
if (!node.left && !node.right) {
2
  // 路径已经到叶子结点，记录并返回
3
}
```
确定单层递归逻辑
- 将当前节点加入路径 const currentPath = path ? path + ' -> ' + node.val : node.val
- 递归处理左右子树

代码#

递归#

1
function binaryTreePaths(root) {
2
  if (!root) return []
3
  const result = []
4

5
  const traverse = (node, path) => {
6
    const currentPath = path ? `${path}->${node.val}` : node.val
7

8
    if (!node.left && !node.right) {
9
      result.push(currentPath)
10
      return
11
    }
12

13
    node.left && traverse(node.left, currentPath)
14
    node.right && traverse(node.right, currentPath)
15
  }
16

17
  traverse(root, '')
18

19
  return result
20
}

404.左叶子之和 🌟#

力扣链接 🌟

题目描述#

给计算给定二叉树的所有左叶子之和。

示例：

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

输出：24（有两个左叶子节点 9 和 15）

解题思路#

关键：如何判断一个节点是左叶子节点

采用后序遍历，先处理叶子节点，再处理父节点，从而就能识别是否为左叶子节点

递归三部曲#

确定递归函数的参数和返回值
- 参数：当前节点
- 返回值：左叶子之和
确定终止条件
- 节点为 null ，返回 0
确定单层递归逻辑
- 计算左子树左叶子之和
- 计算右子树高度左叶子之和
- 如果当前节点的左子节点为左叶子节点 node.left && node.left.left === null && node.left.right === null，则加上当前节点值，否则不加
- 返回 左子树左叶子之和 + 右子树左叶子之和 + 当前节点是否为左叶子节点

代码#

递归#

1
var sumOfLeftLeaves = function (root) {
2
  const nodeSum = (node) => {
3
    if (!node) return 0
4

5
    const leftSum = nodeSum(node.left)
6
    const rightSum = nodeSum(node.right)
7

8
    let midSum = 0
9
    if (node.left && !node.left.left && !node.left.right) {
10
      midSum += node.left.val
11
    }
12

13
    return leftSum + rightSum + midSum
14
  }
15

16
  return nodeSum(root)
17
}

222.完全二叉树的节点个数 🌟#

力扣链接 🌟

题目描述#

给出一个完全二叉树，求出该树的节点个数。

示例 1:

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

示例 2:

输入: root = []
输出: 0

示例 3:

输入: root = [1]
输出: 1

提示:

树中节点的数目范围是[0, 5 * 10^4]
0 <= Node.val <= 5 * 10^4
题目数据保证输入的树是完全二叉树

解题思路#

普通二叉树#

递归三部曲：

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

代码#

1
function countNodes(root) {
2
  const nodeNums = (node) => {
3
    if (!node) return 0
4

5
    const leftNums = nodeNums(node.left)
6
    const rightNums = nodeNums(node.right)
7
    return leftNums + rightNums + 1
8
  }
9

10
  return nodeNums(root)
11
}

完全二叉树#

完全二叉树的特点是最后一层节点尽可能靠左排列，这使得我们可以通过判断子树是否为满二叉树来快速计算节点数（2 ** n - 1）

1
function countNodes(root) {
2
  if (!root) return 0
3

4
  let left = root.left
5
  let right = root.right
6
  let leftDepth = 0, rightDepth = 0
7
  while (lett) {
8
    left = left.left
9
    leftDepth++
10
  }
11
  while (right) {
12
    right = right.right
13
    rightDepth++
14
  }
15

16
  if (leftDepth === rightDepth) {
17
    return Math.pow(2, leftDepth + 1) - 1
18
  }
19
  return countNodes(root.left) + countNodes(root.right) + 1
20
}

音乐

音乐

110.平衡二叉树 🌟#

题目描述#

解题思路#

递归#

257. 二叉树的所有路径 🌟#

题目描述#

解题思路#

代码#

递归#

404.左叶子之和 🌟#

题目描述#

解题思路#

递归三部曲#

代码#

递归#

222.完全二叉树的节点个数 🌟#

题目描述#

解题思路#

普通二叉树#

代码#

完全二叉树#

音乐

文章目录