树的比较与翻转

比较两棵树是否相同用什么框架？

• 框架: 同步递归两棵树的对应位置, 逐层返回布尔值;
• 终止条件: 两者都为空为相同; 只有一个为空为不同; 值不同为不同;
• 复杂度: 时间 O(n), 空间 O(n) 递归栈;

const isSameTree = function (p, q) {
  if (p == null && q == null) return true;
  if (p == null || q == null) return false;
  if (p.val !== q.val) return false;
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

对称二叉树与相同二叉树的区别在哪？

• 相同: 左对左、右对右地比较;
• 对称: 左对右、右对左地比较, 比的是镜像位置;

const isSymmetric = function (root) {
  const dfs = (left, right) => {
    if (left == null && right == null) return true;
    if (left == null || right == null) return false;
    if (left.val !== right.val) return false;
    return dfs(left.left, right.right) && dfs(left.right, right.left);
  };

  return root == null || dfs(root.left, root.right);
};

• 替代做法: 层序遍历时把 null 也补齐, 再逐层判断正序与倒序是否相同;

如何判断一棵树是另一棵树的子树？

• 做法: 遍历大树的每个节点, 用 "相同树" 的判定与目标子树比较;
• 复杂度: 最坏 O(m * n), m、n 分别为两棵树的节点数;

const isSubtree = function (root, subRoot) {
  const isSameTree = (p, q) => {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false;
    if (p.val !== q.val) return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
  };

  const dfs = (node) => {
    if (node == null) return false;
    return isSameTree(node, subRoot) || dfs(node.left) || dfs(node.right);
  };

  return dfs(root);
};

如何翻转二叉树？

• 做法: 后序递归翻转左右子树, 回到当前节点时交换两个子节点;
• 复杂度: 时间 O(n), 空间 O(n) 递归栈;

const invertTree = function (root) {
  if (root == null) return null;
  const left = invertTree(root.left);
  const right = invertTree(root.right);
  root.left = right;
  root.right = left;
  return root;
};