二叉树的比较 - wangshengliang

现在有如下两颗二叉树：

很明显，这两颗二叉树的内容是 完全一致 的，这里我们需要书写一个方法，来判断两颗树是否一致。

// 定义二叉树的节点结构
class TreeNode {
  constructor(value) {
    this.value = value // 节点的值
    this.left = null // 左子树
    this.right = null // 右子树
  }
}

// 构建第一颗二叉树
const a1 = new TreeNode('a')
const b1 = new TreeNode('b')
const c1 = new TreeNode('c')
const d1 = new TreeNode('d')
const e1 = new TreeNode('e')
const f1 = new TreeNode('f')
const g1 = new TreeNode('g')
a1.left = c1
a1.right = b1
c1.left = f1
c1.right = g1
b1.left = d1
b1.right = e1

// 构建第二颗二叉树
const a2 = new TreeNode('a')
const b2 = new TreeNode('b')
const c2 = new TreeNode('c')
const d2 = new TreeNode('d')
const e2 = new TreeNode('e')
const f2 = new TreeNode('f')
const g2 = new TreeNode('g')
a2.left = c2
a2.right = b2
c2.left = f2
c2.right = g2
b2.left = d2
b2.right = e2

/**
 * 比较两棵二叉树是否相同
 * @param {TreeNode|null} tree1 第一棵树的根节点
 * @param {TreeNode|null} tree2 第二棵树的根节点
 * @returns {boolean} 若相同返回 true，否则返回 false
 */
function compareTree(tree1, tree2) {
  // 两个根节点的引用是相同的
  if (tree1 === tree2) return true

  // 如果其中一个为空另一个不为空
  if ((tree1 === null && tree2 !== null) || (tree1 !== null && tree2 === null))
    return false

  // 代码走到这里，说明 tree1 和 tree2 都不为 null
  // 可以访问 value
  if (tree1.value !== tree2.value) return false

  // 递归的判断左右子树是否相同
  const leftResult = compareTree(tree1.left, tree2.left)
  const rightResult = compareTree(tree1.right, tree2.right)

  // 最后，左子树和右子树都必须相同
  return leftResult && rightResult
}

// 调用 compareTree
console.log(compareTree(a1, a2)) // true

有些时候，在进行二叉树比较时，需要确定一个问题，那就是左右两颗子树交换位置算不算同一颗二叉树。比如下面的情况：

可以看到，这两颗二叉树实际上就是左右子树所在位置发生了互换，这在某些场景下会被认为是同一颗二叉树，这就好比：

小明的爸爸和妈妈只是交换了站的位置，但是他们仍然是一家人，不可能换个位置就变成两家人了。

注意：
如果是笔试，没有特殊说明的情况下，左右互换不算同一颗树，如果左右互换算同一颗树，一般题目中会给出特殊的说明。
如果是口头面试，需要当面询问面试官。

// 定义二叉树的节点结构
class TreeNode {
  constructor(value) {
    this.value = value // 节点的值
    this.left = null // 左子树
    this.right = null // 右子树
  }
}

// 构建第一颗二叉树
const a1 = new TreeNode('a')
const b1 = new TreeNode('b')
const c1 = new TreeNode('c')
const d1 = new TreeNode('d')
const e1 = new TreeNode('e')
const f1 = new TreeNode('f')
const g1 = new TreeNode('g')
// 交换 a1 这颗树的左右子树
a1.right = c1
a1.left = b1
c1.left = f1
c1.right = g1
b1.left = d1
b1.right = e1

// 构建第二颗二叉树
const a2 = new TreeNode('a')
const b2 = new TreeNode('b')
const c2 = new TreeNode('c')
const d2 = new TreeNode('d')
const e2 = new TreeNode('e')
const f2 = new TreeNode('f')
const g2 = new TreeNode('g')
a2.left = c2
a2.right = b2
c2.left = f2
c2.right = g2
b2.left = d2
b2.right = e2

/**
 * 比较两棵二叉树是否相同
 * @param {TreeNode|null} tree1 第一棵树的根节点
 * @param {TreeNode|null} tree2 第二棵树的根节点
 * @returns {boolean} 若相同返回 true，否则返回 false
 */
function compareTree(tree1, tree2) {
  // 两个根节点的引用是相同的
  if (tree1 === tree2) return true

  // 如果其中一个为空另一个不为空
  if ((tree1 === null && tree2 !== null) || (tree1 !== null && tree2 === null))
    return false

  // 代码走到这里，说明 tree1 和 tree2 都不为 null
  // 可以访问 value
  if (tree1.value !== tree2.value) return false

  // 递归的判断左右子树是否相同
  // const leftResult = compareTree(tree1.left, tree2.left);
  // const rightResult = compareTree(tree1.right, tree2.right);

  // 最后，左子树和右子树都必须相同
  // return leftResult && rightResult;

  const result1 =
    compareTree(tree1.left, tree2.left) && compareTree(tree1.right, tree2.right)
  const result2 =
    compareTree(tree1.left, tree2.right) && compareTree(tree1.right, tree2.left)
  return result1 || result2
}

// 调用 compareTree
console.log(compareTree(a1, a2)) // true

-EOF-