Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
1 / \ 2 2 / \ / \ 3 4 4 3
But the following is not:
1 / \ 2 2 \ \ 3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
Understand the problem:Bonus points if you could solve it both recursively and iteratively.
The problem asks for checking if a tree is a mirror of itself, i.e, symmetric around its center.
We can take several examples to show the problem:
Besides the two examples shown above,
An empty is symmetric.
A tree with only 1 node is symmetric.
1
/ \
3 4
is not symmetric.
Recursive Solution:
It is not hard to find that if a tree is symmetric, its inorder traversal list should be symmetric as well. For instance, for the first example, its inorder traversal is 3,2,4,1,4,2,3. Since the list is symmetric, the tree is symmetric as well.
For the second example, its inorder traversal is 2,3,1,2,3, which is not symmetric.
So one straight-forward solution is to traverse the tree in-order ,save it to an array list. Then check the array list is symmetric.
Wrong Answer:
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
ArrayList<Integer> result = new ArrayList<Integer>();
inOrderTraversal(root, result);
return isSymmetricArray(result);
}
private void inOrderTraversal(TreeNode root, ArrayList<Integer> result) {
if (root == null) return;
inOrderTraversal(root.left, result);
result.add(root.val);
inOrderTraversal(root.right, result);
}
private boolean isSymmetricArray(ArrayList<Integer> result) {
int start = 0;
int end = result.size() - 1;
while (start < end) {
if (result.get(start) != result.get(end)) return false;
start++;
end--;
}
return true;
}
}
The code itself has nothing wrong, but the inorder traversal will result in the following wrong answer:
| Input: | {1,2,3,3,#,2,#} |
| Output: | true |
| Expected: | false |
Correct Solution:
So we must come out another solution. For a symmetric tree, the left child and right child of the root must be equal. Then for those two nodes, the left node's left child must be equal to the right node's right child; the left node's right child must be equal to the right node's left child. Then we recursively repeats those process until both nodes are null.
Code (Java):
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return isSymmetric(root.left, root.right);
}
private boolean isSymmetric(TreeNode a, TreeNode b) {
if (a == null) return b == null;
else if (b == null) return false;
if (a.val != b.val) return false;
if (isSymmetric(a.left, b.right) == false) return false;
if (isSymmetric(a.right, b.left) == false) return false;
return true;
}
}
Iterative Solution:
The iterative solution could borrow the idea of BFS, so we still use a queue to store intermediate results. Instead of using a queue, we used two queues, the left queue stores the left children, while the right queue stores the right children. We start from the root node, and enqueue its left and right child into the right and right queue, respectively, if left and right child existed. Then like the BFS, we dequeue two elements from the left and right queue each, and check if it is equal. If not, return false. Then we enqueue the left node's left child and right node's right child into the corresponding queue. And we enqueue left node's right child and right node's left child into the queue. We repeat this process until the queues are empty.
Code (Java):
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
Queue<TreeNode> lQueue = new LinkedList<TreeNode>();
Queue<TreeNode> rQueue = new LinkedList<TreeNode>();
if (root.left != null) lQueue.offer(root.left);
if (root.right != null) rQueue.offer(root.right);
while (!lQueue.isEmpty() || !rQueue.isEmpty()) {
int size = Math.max(lQueue.size(), rQueue.size());
for (int i = 0; i < size; i++) {
if (lQueue.isEmpty() || rQueue.isEmpty()) return false;
TreeNode a = lQueue.poll();
TreeNode b = rQueue.poll();
if (a.val != b.val) return false;
if (a.left != null) lQueue.offer(a.left);
if (b.right != null) rQueue.offer(b.right);
if (a.right != null) rQueue.offer(a.right);
if (b.left != null) lQueue.offer(b.left);
}
}
return true;
}
}
Summary:
The crux of the problem is to know how to determine if a tree is symmetric. If you know to compare two nodes' left and right children respectively, the problem becomes quite easy. An error-prone approach was showed. The mainly reason to come out that approach is to categorize a question into either BFS or DFS. Analogy is definitely helpful, but it is more important to go back the nature of the problem, and analyze what the problem asks for on earth. So be very careful about understanding the problem and deducing your solution.
Update on 10/7/14:
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
Queue lQueue = new LinkedList();
Queue rQueue = new LinkedList();
lQueue.offer(root);
rQueue.offer(root);
while (!lQueue.isEmpty() && !rQueue.isEmpty()) {
TreeNode curLeft = lQueue.poll();
TreeNode curRight = rQueue.poll();
if (curLeft.val != curRight.val) {
return false;
}
if (curLeft.left != null) {
lQueue.offer(curLeft.left);
}
if (curRight.right != null) {
rQueue.offer(curRight.right);
}
if (curLeft.right != null) {
rQueue.offer(curLeft.right);
}
if (curRight.left != null) {
lQueue.offer(curRight.left);
}
}
if (!lQueue.isEmpty() || !rQueue.isEmpty()) {
return false;
} else {
return true;
}
}
}
Update on 4/14/15:
Iterative solution with allowing to add null into the queue.
public class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
Queue<TreeNode> lQueue = new LinkedList<TreeNode>();
Queue<TreeNode> rQueue = new LinkedList<TreeNode>();
lQueue.offer(root.left);
rQueue.offer(root.right);
while (!lQueue.isEmpty()) {
TreeNode a = lQueue.poll();
TreeNode b = rQueue.poll();
if (a == null && b != null) {
return false;
}
if (b == null && a != null) {
return false;
}
if (a != null && b != null && a.val != b.val) {
return false;
}
if (a != null) {
lQueue.offer(a.left);
lQueue.offer(a.right);
}
if (b != null) {
rQueue.offer(b.right);
rQueue.offer(b.left);
}
}
return true;
}
}
No comments:
Post a Comment