[LeetCode]--101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

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

Note: Bonus points if you could solve it both recursively and iteratively.

一开始我就想到了递归算法，看图写程序嘛，简单可靠。

public boolean isSymmetric(TreeNode root) { if (root == null) return true; return testSymmetric(root.left, root.right); } public boolean testSymmetric(TreeNode left, TreeNode right) { if (left == null && right == null) return true; if ((left == null && right != null) || (left != null && right == null)) return false; if (left != null && right != null && left.val != right.val) return false; return testSymmetric(left.left, right.right) && testSymmetric(left.right, right.left); }

我尝试了一下非递归算法，没写出来【衰】。还好递归时间通过了，也挺好。看了下LeetCode官方讨论区。

Approach #1 (Recursive) [Accepted]

public boolean isSymmetric(TreeNode root) { return isMirror(root, root); } public boolean isMirror(TreeNode t1, TreeNode t2) { if (t1 == null && t2 == null) return true; if (t1 == null || t2 == null) return false; return (t1.val == t2.val) && isMirror(t1.right, t2.left) && isMirror(t1.left, t2.right); }

Approach #2 (Iterative) [Accepted]

public boolean isSymmetric(TreeNode root) { Queue<TreeNode> q = new LinkedList<>(); q.add(root); q.add(root); while (!q.isEmpty()) { TreeNode t1 = q.poll(); TreeNode t2 = q.poll(); if (t1 == null && t2 == null) continue; if (t1 == null || t2 == null) return false; if (t1.val != t2.val) return false; q.add(t1.left); q.add(t2.right); q.add(t1.right); q.add(t2.left); } return true; }

这个非递归算法写的真是帅啊，用队列。

LeetCode官方讨论区