二叉树系列

, 评论

(搜索)二叉树这种数据结构，操作和判断特别多，这篇文章归纳和整理一下它的常见操作。一个有趣的现象是，关于二叉树，有广度优先和深度优先两种搜索办法。如果是广度优先，常规做法是使用一个辅助队列 queue。如果是深度优先，常规做法是使用递归。

  • 验证二叉搜索树
  • 对称二叉树
  • 二叉树的前中后序遍历
  • 二叉树的层次遍历/锯形层次遍历
  • 二叉树最近公共祖先
  • 二叉树最大/最小深度
  • 删除二叉树中的节点
  • 从中序遍历和后序遍历构造二叉树

验证二叉搜索树 98

验证一棵树是否为二叉搜索树，有两种方法。都是基于二叉搜索树的特征。

  • 基于二叉搜索树的中序遍历结果是升序序列。
    • 中序遍历整个二叉搜索树，遍历的过程中查验是否为升序。
  • 基于节点的左子树中所有的节点的值，均小于当前节点的值；节点的右子树中所有节点的值，均大于当前节点的值。
    • 根节点的值的范围为(-Infinity,Infinity)。其左子节点的值应该小于 root.val, 所以范围应该为(-Infinity,root.val)。同理，右子节点的范围应该为(root.val,Infinity)。树上的每个节点都应该满足上面的条件。

递归代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function helper(root: TreeNode | null, min: number, max: number): boolean {
  if (!root) return true;
  // 不满足条件
  if (root.val <= min || root.val >= max) {
    return false;
  }
  // 递归验证左右孩子是否满足条件
  return helper(root.left, min, root.val) && helper(root.right, root.val, max);
}

function isValidBST(root: TreeNode | null): boolean {
  // root节点的取值范围为(-Infinity,Infinity)
  return helper(root, -Infinity, Infinity);
}

对称二叉树 剑指 offer28

验证一个树是否为对称二叉树，优雅的方案还是递归，毕竟要一层一层的比较，而且每次比较的模式都是一样的。

递归代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function helper(left: TreeNode | null, right: TreeNode | null): boolean {
  if (!left && !right) {
    // 都不存在
    return true;
  } else if (left && right) {
    if (left.val === right.val) {
      // 当前两个节点是对称的，继续去验证他们的孩子是否对称
      return helper(left.left, right.right) && helper(left.right, right.left);
    } else {
      // 不对称相等
      return false;
    }
  } else {
    // left或者right，只存在一个
    return false;
  }
}

function isSymmetric(root: TreeNode | null): boolean {
  return helper(root, root);
}

二叉树的前中后序遍历 94

这里以二叉树的中序遍历为例子。使用递归，中序遍历的实现很容易实现（代码简单）。比较难（或者说不容易记住和理解）的是使用迭代的方式来遍历。
不过话说回来，明明递归的代码看上去更简洁明了，可能是更符合人们的思维习惯。相反如果是使用迭代，确需要肯定的理解其执行过程 😖。

递归代码

1
2
3
4
5
6
7
8
9
10
11
12
13
function helper(root: TreeNode | null, res: number[]) {
  if (!root) return;

  helper(root.left, res);
  res.push(root.val);
  helper(root.right, res);
}

function inorderTraversal(root: TreeNode | null): number[] {
  const res: number[] = [];
  helper(root, res);
  return res;
}

迭代代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function inorderTraversal(root: TreeNode | null): number[] {
  if (!root) return [];

  const res = [];
  // 既然是递归，就要用栈来模拟咯
  const stack = [];
  while (stack.length || root) {
    while (root) {
      stack.push(root);
      root = root.left;
    }

    // 此时的root为null，栈顶元素就是最左边的叶子节点
    // 弹出并访问
    const node = stack.pop();
    res.push(node.val);

    // 这一步很关键，开始准备遍历右子树
    root = node.right;
  }
  return res;
}

二叉树的层次遍历

  • 使用递归，也就是 dfs 深度优先搜索。
  • 可以使用一个队列来保存被访问的节点，也就是广度优先搜索。

递归代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function helper(root: TreeNode | null, index: number, res: number[][]) {
  if (!root) return;

  res[index] ? res[index].push(root.val) : (res[index] = [root.val]);

  helper(root.left, index + 1, res);
  helper(root.right, index + 1, res);
}

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const res = [];
  helper(root, 0, res);
  return res;
}

迭代代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const queue = [root];
  const res = [];
  while (queue.length) {
    const length = queue.length;
    const temp = [];
    for (let i = 0; i < length; i++) {
      const node = queue.shift();
      temp.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    res.push(temp);
  }
  return res;
}

二叉树最近公共祖先

前提条件是 p 和 q 都是树中的节点。

递归代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode | null,
  q: TreeNode | null
): TreeNode | null {
  if (!root) return root;
  if (root === p || root === q) return root;

  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  if (left && right) {
    return root;
  } else if (left) {
    return left;
  } else {
    return right;
  }
}

二叉树的最大深度

递归求出左右子树深度的最大值，然后加 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

function minDepth(root: TreeNode | null): number {
  if (!root) return 0;
  if (!root.left && !root.right) return 1;
  let min = Infinity;
  if (root.left) {
    min = Math.min(minDepth(root.left), min);
  }
  if (root.right) {
    min = Math.min(minDepth(root.right), min);
  }
  return min + 1;
}