LC-对称二叉树

发表于 更新于 分类于

题目描述

对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1
2
3
4
5
    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

1
2
3
4
5
  1
 / \
2   2
 \   \
 3    3

代码实现

DFS（递归）

递归比迭代要简单很多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
  if (!root) {
    return true;
  }
  function DFS(l, r) {
    if (!l && !r) {
      return true;
    }
    if ((!l && r) || (l && !r) || (l.val !== r.val)) {
      return false;
    }
    return DFS(l.right, r.left) && DFS(l.left, r.right)
  }
  return DFS(root.left, root.right)
};

BFS（队列 + 迭代）

队列 + 迭代的实现方式

这里的 while (q1.length && q2.length) 少了 length 就会一直执行下去，因为 Boolean([]) 为 true，这里的q指代 队列，shift 方法为删除数组的第一个元素并返回第一个元素的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
  if (!root) {
    return true;
  }
  let q1 = [root.left];
  let q2 = [root.right];
  while (q1.length || q2.length) {
    let n1 = q1.shift();
    let n2 = q2.shift();
    if (!n1 && !n2) {
      continue;
    }
    if ((n1 && !n2) || (!n1 && n2) || (n1.val !== n2.val)) {
      return false;
    }
    q1.push(n1.left);
    q1.push(n1.right);
    q2.push(n2.right);
    q2.push(n2.left);
  }
  return true;
};