对称二叉树

Posted on | In
对称二叉树

如果一棵二叉树和它的镜像一样，那么它是对称的。例如

1
2
3
4
5
     8
   /   \
  6     6
 / \   / \
5   7 7   5

是一棵对称的二叉树

而以下的不是

1
2
3
4
5
     8
   /   \
  6     6
 /     / \
5      7  5

结构不对称

1
2
3
4
5
      8
    /   \
  6      6
 / \    / \
5  6    7  5

数值不对称

下面给出判断二叉树是否对称的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Tree.prototype.isSymmetrical = function () {
  if (this.root === null) {
    return true
  }
  return this.isMirror(this.root.left, this.root.right)
}

Tree.prototype.isMirror = function (node1, node2) {
  if (node1 === null && node2 === null) {
    return true
  }

  if (node1 === null || node2 === null) {
    return false
  }

  // 左右子节点相同，且左子节点的左子节点和右子节点的右子节点对称
  return node1.label === node2.label ?
    this.isMirror(node1.left, node2.right) && this.isMirror(node1.right, node2.left) :
    false
}

而把一个二叉树转换为他的镜像可以按如下操作：

1
2
3
4
5
6
7
8
Tree.prototype._toMirror = function (node) {
  if (node === null) return
  var tmp = node.left
  node.left = node.right
  node.right = tmp
  this._toMirror(node.left)
  this._toMirror(node.right)
}