怎样求二叉树的最大深度、翻转二叉树、判断对称二叉树？

简答

这三题是二叉树递归的入门题。最大深度是从根走到最远叶子经过的节点数；翻转二叉树是把整棵树左右镜像过来；对称二叉树是判断一棵树和它自己的镜像是不是一样。

写递归的思路都一样：先想清楚空树返回什么，再假设子树的结果已经算好，看当前节点怎么用这两个结果。最大深度是 max(左深度, 右深度) + 1；翻转是交换左右子节点，再各自翻转；对称要写一个同时接收两个节点的辅助函数，比较两边的值，再递归比较“左的左和右的右”“左的右和右的左”。

这类分解很常见，比如计算组件树的嵌套层数、把左右布局镜像过来、判断两份树形配置是不是一样，都是同样的递归。

要注意，对称不是“左子树等于右子树”，而是左子树等于右子树的镜像，比较时外侧对外侧、内侧对内侧。三题都是 O(n) 时间，递归深度等于树高，树退化成链时可能很深，这时可以改用队列或栈迭代。

三题的写法

fromLevelOrder 按 LeetCode 的层序数组建树，toLevelOrder 把树转回数组方便打印。重点看 isMirror 两次递归传的是哪两个节点。

JavaScript

function fromLevelOrder(values) {
  if (values.length === 0 || values[0] === null) return null;
  const root = { val: values[0], left: null, right: null };
  const queue = [root];
  let i = 1;
  for (let head = 0; i < values.length; head++) {
    const node = queue[head];
    for (const side of ['left', 'right']) {
      if (i < values.length && values[i] !== null) {
        node[side] = { val: values[i], left: null, right: null };
        queue.push(node[side]);
      }
      i++;
    }
  }
  return root;
}

function toLevelOrder(root) {
  const result = [];
  const queue = [root];
  for (let head = 0; head < queue.length; head++) {
    const node = queue[head];
    result.push(node ? node.val : null);
    if (node) queue.push(node.left, node.right);
  }
  while (result.length && result[result.length - 1] === null) result.pop();
  return JSON.stringify(result);
}

function maxDepth(root) {
  if (!root) return 0;
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

function invertTree(root) {
  if (!root) return null;
  [root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
  return root;
}

function isSymmetric(root) {
  return isMirror(root?.left ?? null, root?.right ?? null);
}

function isMirror(a, b) {
  if (!a || !b) return a === b;
  return a.val === b.val && isMirror(a.left, b.right) && isMirror(a.right, b.left);
}

console.log(maxDepth(fromLevelOrder([3, 9, 20, null, null, 15, 7]))); // 3
console.log(maxDepth(fromLevelOrder([1, null, 2]))); // 2
console.log(maxDepth(fromLevelOrder([]))); // 0

console.log(toLevelOrder(invertTree(fromLevelOrder([4, 2, 7, 1, 3, 6, 9])))); // [4,7,2,9,6,3,1]
console.log(toLevelOrder(invertTree(fromLevelOrder([2, 1, 3])))); // [2,3,1]

console.log(isSymmetric(fromLevelOrder([1, 2, 2, 3, 4, 4, 3]))); // true
console.log(isSymmetric(fromLevelOrder([1, 2, 2, null, 3, null, 3]))); // false
console.log(isSymmetric(fromLevelOrder([1, 2, 2, 3, 4, 3, 4]))); // false

maxDepth 为什么空树返回 0？深度按节点数算，空树没有节点。叶子节点左右都是 0，加 1 得到 1，正好是它自己这一个节点，往上每层再加 1。

invertTree 里交换和递归写在一行，右边的数组先算完两次递归，再整体赋值给左右两边，所以不会出现“先改了 root.left 再去翻转它”的问题。拆成几行写时，要先用临时变量存住一边。

最后一个对称的例子说明了为什么不能简单比较左右子树。[1,2,2,3,4,3,4] 的左子树是 2 下面挂 3、4，右子树也是 2 下面挂 3、4，两边完全一样，但镜像要求左边的 3 对着右边的 4，所以不对称。isMirror 第一行处理了空节点：两个都空算对称，只有一个空就不对称，a === b 正好同时表达这两种情况。

不用递归怎么写

最大深度可以用层序遍历数层数，见《二叉树怎样层序遍历、求最大深度？》。对称二叉树可以用队列，每次成对放入 (a.left, b.right) 和 (a.right, b.left)，成对取出比较。翻转二叉树用栈或队列都行，取出一个节点就交换它的左右子节点，再把子节点放进去，访问顺序不影响结果，因为每个节点只需要交换一次。

常见追问

最小深度能不能把 max 换成 min？

不能直接换。最小深度是到最近的叶子节点，如果一个节点只有右子树，左边是空的，min 会取到 0，把它算成叶子。要单独处理：一边为空时用另一边的深度加 1，两边都有时才取较小值。

怎么判断两棵树完全相同？

和 isMirror 几乎一样，只是递归改成比较 a.left 和 b.left、a.right 和 b.right。

翻转二叉树会创建新节点吗？

上面的写法是原地修改，返回的还是原来的根节点，只是每个节点的左右指针交换了。如果需要保留原树，就在递归里新建节点，左子节点取翻转后的右子树，右子节点取翻转后的左子树。