leetcode-101-105-23-使用递归吧

评论

101-105-23 使用递归吧

  • 101 对称二叉树
  • 105 根据中序遍历和先序遍历构造二叉树
  • 23 合并 k 个升序链表

这几个问题虽然情景各不一样，但是都可以使用递归的编程技巧来解决问题。

101 对称二叉树

使用递归

  1. 使用两个指针 p 和 q，初始化都指向 root 节点。
  2. 判断 p.val===q.val，如果相等那么 p 和 q 同时移动，但是移动的方向是对称的，也就是 p 向左移动，那么 q 就要向右移动。
  3. 由于要比较和操作 p 和 q 两个指针，因此我们的函数也需要两个参数

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function helper(p: TreeNode | null, q: TreeNode | null): boolean {
  if (!p && !q) return true;
  if (!p || !q) return false;

  if (p.val !== q.val) return false;

  const inner = helper(p.left, q.right); // 验证内对称
  const outer = helper(p.right, q.left); // 验证外对称

  return inner && outer;
}

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

这里的为了验证对称性，内部调用了两次 helper，这也算是树的递归常见模式，针对不同的情况，分开递归调用。
其中 helper 还可以简写为如下形式。

1
2
3
4
5
6
function helper(p: TreeNode | null, q: TreeNode | null): boolean {
  if (!p && !q) return true;
  if (!p || !q) return false;

  return p.val === q.val && helper(p.left, q.right) && helper(p.right, q.left);
}