LeetCode 101. Symmetric Tree

101. Symmetric Tree（对称二叉树）

链接

https://leetcode-cn.com/problems/symmetric-tree

题目

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

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

1

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

1

/
2 2
\
3 3
说明:

如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

思路

树的题目，尤其是二叉树，用递归和迭代都能减少运算量，这里用递归。
首先是根节点的判断，为空那么符合，之后就是递归过程，先查看左右子节点，相同的话继续比较左子树左节点和右子树右节点，左子树右节点和右子树左节点，如果不同，直接false。

代码

public class TreeNode {

  int val;
  TreeNode left;
  TreeNode right;

  TreeNode(int x) {
    val = x;
  }
}

public boolean test(TreeNode l, TreeNode r) {
  if (l == null && r == null) {
    return true;
  }
  if (l == null || r == null) {
    return false;
  }
  if (l.val == r.val) {
    return test(l.left, r.right) && test(l.right, r.left);
  } else {
    return false;
  }
}

public boolean isSymmetric(TreeNode root) {
  if (root == null) {
    return true;
  } else {
    return test(root.left, root.right);
  }
}