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

235. 二叉搜索树的最近公共祖先 🌟🌟#

力扣链接 🌟🌟

题目描述#

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

百度百科中最近公共祖先的定义为：“对于有根树 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
// 输出 树根节点
2
//       6
3
//      / \
4
//     2   8
5
//    / \ / \
6
//   0  4 7 9
7
//     / \
8
//    3  5

解题思路#

二叉搜索树

p 和 q 值都小于当前节点值时，p 和 q 的最近公共祖先就在左子树
p 和 q 值都大于当前节点值时，p 和 q 的最近公共祖先就在右子树
否则，当前节点就是 p 和 q 的最近公共祖先（此时 p 和 q 分布在当前节点的两侧，或其中一个等于当前节点）

如上述二叉搜索树：如果 2 处于[p, q]之间时，此时 p 就在节点 2 的左子树，q 在节点 2 的右子树，那么 2 就一定是 p 和 q 的最近公共祖先。

递归三部曲：

明确递归函数的参数和返回值
- 参数 1：当前节点
- 参数 2：p
- 参数 3
- 返回值：最近公共节点
明确终止条件
- 当节点为 null 返回 null
确定单层递归逻辑
- p 和 q 值都大于当前节点值时，继续遍历左子树
- p 和 q 值都小于当前节点值时，继续遍历右子树
- 否则，返回当前节点
```
1
if (cur.val > p.val && cur.val > q.val)
2
  if (cur.val < p.val && cur.val < q.val)
3
    // 遍历左子树
4
    // 遍历右子树
5
    return cur
```

1
function lowestCommonAncestor(root, p, q) {
2
  if (!root) return null
3

4
  if (root.val > p.val && root.val > q.val) {
5
    return lowestCommonAncestor(root.left, p, q)
6
  } else if (root.val < p.val && root.val < q.val) {
7
    return lowestCommonAncestor(root.right, p, q)
8
  } else {
9
    return root
10
  }
11
}

1
// 迭代法
2
var lowestCommonAncestor = function (root, p, q) {
3
  if (!root) return null
4
  while (root) {
5
    if (root.val < p.val && root.val < q.val) {
6
      return lowestCommonAncestor(root.right, p, q)
7
    }
8
    if (root.val > p.val && root.val > q.val) {
9
      return lowestCommonAncestor(root.left, p, q)
10
    }
11
    return root
12
  }
13
}

701.二叉搜索树中的插入操作 🌟🌟#

力扣链接 🌟🌟

题目描述#

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。

示例:

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

9
// 返回二叉树
10
//       4
11
//      / \
12
//     2   7
13
//    /\  /
14
//   1 3 5
15
// 或者这个树也是有效的
16
//       5
17
//      / \
18
//     2   7
19
//    / \
20
//   1  3
21
//      \
22
//      4

提示：

给定的树上的节点数介于 0 和 10^4 之间
每个节点都有一个唯一整数值，取值范围从 0 到 10^8
-10^8 <= val <= 10^8
新值和原始二叉搜索树中的任意节点值都不同

#

解题思路#

递归#

递归三部曲：

确定递归函数的参数和返回值
- 参数 1：当前节点
- 参数 2：要插入的值
- 返回值：root
确定终止条件

如果当前节点为 null，则根据值创建新节点
```
1
if (!root1) return new TreeNode(val)
```
确定单层递归逻辑
- 当前节点值大于 val，继续遍历左子树
- 当前节点值小于 val，继续遍历右子树
- 否则，返回返回当前节点

1
function insertIntoBST(root, val) {
2
  const setInOrder = (root, val) => {
3
    if (!root) return new TreeNode(val)
4

5
    if (root.val > val) root.left = setInOrder(root.left, val)
6
    if (root.val < val) root.right = setInOrder(root.right, val)
7

8
    return root
9
  }
10

11
  return setInOrder(root, val)
12
}

迭代#

步骤：

记录当前节点 root 以及父节点 parent（初始化时定义）
循环遍历当前节点，比较当前节点值和插入值
如果当前节点不为空，更新当前节点为左或右子节点，同时更新父节点
如果当前节点为空，根据父节点的值和插入值的大小，决定插入到左还是右
返回 root

1
function insertIntoBST(root, val) {
2
  if (!root) {
3
    return new TreeNode(val)
4
  } else {
5
    let parent = null
6
    let cur = root
7
    while (cur) {
8
      parent = cur
9
      if (cur.val > val) {
10
        cur = cur.left
11
      } else {
12
        cur = cur.right
13
      }
14
    }
15
    let node = new TreeNode(val)
16
    if (parent.val > val) {
17
      parent.left = node
18
    } else {
19
      parent.right = node
20
    }
21
  }
22
  return root
23
}

450.删除二叉搜索树中的节点 🌟🌟#

力扣链接 🌟🌟

题目描述#

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

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

首先找到需要删除的节点；如果找到了，删除它。说明：要求算法时间复杂度为 $O(h)$ ，h 为树的高度。

示例:

解题思路#

删除节点情况：

没找到删除节点，则返回 null
删除节点是叶子节点，直接删除，不影响其他节点
删除节点只有一个子节点，删除节点，并用子节点替换删除节点
删除节点有两个子节点，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上（右子树中最小值），返回删除节点右孩子为新的根节点

递归#

递归三部曲：

确定递归函数的参数和返回值
- 参数 1：根节点
- 参数 2：要删除的值
- 返回值：搜索的值所在的节点
确定终止条件

如果 root 为 null 则说明没找到删除的节点，返回 root
```
1
if (!root) return root
```
确定单层递归逻辑
- 要删除的值大于 root.val，则继续递归右子树
- 要删除的值小于 root.val，则继续递归左子树
- 要删除的值就是当前节点时：
  - 节点是叶子结点
  - 节点只有一个子节点，则返回
  - 左右节点都存在，将将当前节点的左子树头节点指向右子树最左边节点，并将右子树指向删除节点的父节点

1
function deleteNode(root, key) {
2
  if (!root) return root
3
  if (root.val > key) {
4
    root.left = deleteNode(root.left, key)
5
  } else if (root.val < key) {
6
    root.right = deleteNode(root.right, key)
7
  } else {
8
    if (!root.left && !root.right) return null
9
    if (!root.left && root.right) return root.right
10
    if (!root.right && root.left) return root.left
11

12
    const rightNode = root.right
13
    const minNode = getMinNode(root.right)
14
    root.val = minNode.val
15
    root.right = deleteNode(rightNode, minNode.val)
16
  }
17
  return root
18
}
19
function getMinNode(node) {
20
  while (node.left) node = node.left;
21
  return node;
22
}

迭代#

1
function deleteNodeIterative(root, key) {
2
  let parent = null;
3
  let current = root;
4

5
  // 查找目标节点
6
  while (current && current.val !== key) {
7
    parent = current;
8
    current = key < current.val ? current.left : current.right;
9
  }
10

11
  if (!current) return root; // 未找到
12

13
  // Case 1: 无子节点
14
  if (!current.left && !current.right) {
15
    if (!parent) return null; // 删除根节点
16
    parent[current === parent.left ? 'left' : 'right'] = null;
17
    return root;
18
  }
19

20
  // Case 2: 单个子节点
21
  if (!current.left || !current.right) {
22
    const child = current.left || current.right;
23
    if (!parent) return child; // 删除根节点
24
    parent[current === parent.left ? 'left' : 'right'] = child;
25
    return root;
26
  }
27

28
  // Case 3: 两个子节点
29
  const successorParent = current;
30
  let successor = current.right;
31
  while (successor.left) {
32
    successorParent = successor;
33
    successor = successor.left;
34
  }
35

36
  current.val = successor.val;
37
  if (successorParent === current) {
38
    successorParent.right = successor.right;
39
  } else {
40
    successorParent.left = successor.right;
41
  }
42

43
  return root;
44
}

音乐

音乐

235. 二叉搜索树的最近公共祖先 🌟🌟#

题目描述#

解题思路#

701.二叉搜索树中的插入操作 🌟🌟#

题目描述#

#

解题思路#

递归#

迭代#

450.删除二叉搜索树中的节点 🌟🌟#

题目描述#

解题思路#

递归#

迭代#

音乐

文章目录