[LeetCode] 101. Symmetric Tree

判断对称树。题意是给一个树，判断它是不是左右对称/轴对称的。例子

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
    1
   / 
  2   2
 /  / 
3  4 4  3
But the following [1,2,2,null,3,null,3] is not:
    1
   / 
  2   2
      
   3    3

题目很简单，跟100题几乎一样，也是用DFS思路做。唯一不同的地方是当判断子树的时候，100题是判断left.left == right.left；而这题是判断left.right == right.left

时间O(n)

空间O(n)

JavaScript实现

 1 /**
 2  * @param {TreeNode} root
 3  * @return {boolean}
 4  */
 5 var isSymmetric = function(root) {
 6     if (root === null) return true;
 7     return helper(root.left, root.right);
 8 };
 9 
10 var helper = function(left, right) {
11     if (left === null && right === null) return true;
12     if (left === null || right === null) return false;
13     if (left.val !== right.val) return false;
14     return helper(left.left, right.right) && helper(left.right, right.left);
15 };

Java实现

 1 class Solution {
 2     public boolean isSymmetric(TreeNode root) {
 3         if (root == null)
 4             return true;
 5         return helper(root.left, root.right);
 6     }
 7 
 8     private boolean helper(TreeNode p, TreeNode q) {
 9         if (p == null && q == null)
10             return true;
11         if (p == null || q == null)
12             return false;
13         if (p.val != q.val)
14             return false;
15         return helper(p.left, q.right) && helper(p.right, q.left);
16     }
17 }

BFS解法

时间O(n)

空间O(n)

JavaScript实现

 1 /**
 2  * @param {TreeNode} root
 3  * @return {boolean}
 4  */
 5 var isSymmetric = function(root) {
 6     const q = [root, root];
 7     while (q.length) {
 8         const [l, r] = [q.shift(), q.shift()];
 9         if (!l && !r) continue;
10         if (!!l !== !!r || l.val !== r.val) return false;
11         q.push(l.left, r.right, l.right, r.left);
12     }
13     return true;
14 };