101. 对称二叉树

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

例如，二叉树 [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
说明:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/symmetric-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

运用先序遍历的非递归算法，和逆后序遍历的非递归算法进行遍历比对即可。不过时间复杂度排名不高。

 1 public class Solution {
 2
 3     public boolean isSymmetric(TreeNode root) {
 4         if (root == null) return true;
 5         // 先序遍历的非递归算法 与 后序遍历的非递归算法
 6         Stack<TreeNode> pre = new Stack<>();
 7         Stack<TreeNode> post = new Stack<>();
 8         TreeNode p = root, q = root;
 9
10         do {
11             for (TreeNode i = p, j = q; i != null; i = i.left, j = j.right) {
12                 // 访问节点
13                 try {
14                     if (i.val != j.val)
15                         return false;
16                 } catch (NullPointerException e) {
17                     return false;
18                 }
19                 pre.push(i);
20                 post.push(j);
21             }
22
23             p = pre.pop().right;
24             q = post.pop().left;
25         } while (p != null || !pre.empty());
26         return true;
27     }
28
29     public static void main(String[] args) {
30         //1, 2, 2, 3, 4, 4, 3
31         //1,2,2,null,3,null,3
32         //1,2,3,null,4,5,null
33         TreeNode p = _94.create(new Object[]{1,2,2,null,3,null,3});
34         boolean symmetric = new Solution().isSymmetric(p);
35         System.out.println("\nsymmetric = " + symmetric);
36     }
37 }