[Leetcode 7] 101 Symmetric Tree

Problem:

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

For example, this binary tree is symmetric:

But the following is not:

Analysis:

Recursion can help in this problem. Write a helper function which accepts two TreeNode arguments, if all of them are null, return true; only one of them is null, return false; both of them are not null, if t1.val != t2.val, return false, else compare t1.left with t2.right and t1.right with t2.left. Most of this check is the same as Same Tree problem, the only difference is when current two nodes are the same, instead of checking two node's children corresponding, we check left with right and right with left. The recursion is so fantastic!!!

Another way to solve this problem is to use iterative method.

The basic thought is use two queues, one is used to store the left sub tree of root node, we call it queueLeft; and the other is used to stroe the right sub tree of root node, we call it queueRight;

queueLeft always enqueues the current node's left child and then right child; queueRight performs on the contrary way, always enqueues the current node's right child first and then its left child. To deal with node only has one child case, we introduce the nullNode to represent such a null to keep the basic structure of the binary tree. Then we continue dequeue, compare, and then enqueue.

There is a tricky problem in this solution. Given a tree as follows:

          1
       /    \
      2      2
     / \    / \
    3   4   4  3
       / \    / \
      8   9   9  8

If we just enqueue those null Node into each queue, the result of this tree is true, which actually is false. So we must make sure that, enqueue performs on the same structure of child nodes.

Code:

Recursive Version

Inerative Version

 1 /**
 2  * Definition for binary tree
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public boolean isSymmetric(TreeNode root) {
12         // Start typing your Java solution below
13         // DO NOT write main() function
14         Queue<TreeNode> ql = new LinkedList<TreeNode>();
15         Queue<TreeNode> qr = new LinkedList<TreeNode>();
16         TreeNode nullNode = new TreeNode(Integer.MIN_VALUE);
17         
18         if (root == null) return true;
19         
20         enqueue(root.left, ql, nullNode);
21         enqueue(root.right, qr, nullNode);
22         
23         while (!ql.isEmpty() && !qr.isEmpty()) {
24             TreeNode tl = ql.remove();
25             TreeNode tr = qr.remove();
26             
27             if (tl.val == tr.val) {
28                 if (tl.left!=null && tr.right!=null) {
29                     enqueue(tl.left, ql, nullNode);
30                     enqueue(tr.right, qr, nullNode);
31                 }
32                 
33                 if (tl.right!=null && tr.left!=null) {
34                     enqueue(tl.right, ql, nullNode);
35                     enqueue(tr.left, qr, nullNode);
36                 }
37                 
38                 
39                 if ((tl.left==null && tr.right!=null) ||
40                      (tl.left!=null && tr.right==null) ||
41                      (tl.right==null && tr.left!=null) ||
42                      (tl.right!=null && tr.left==null))
43                     return false;
44             } else
45                 return false;
46         }
47             
48         
49         return (ql.isEmpty()) && (qr.isEmpty());
50     }
51     
52     private void enqueue(TreeNode node, Queue<TreeNode> q, TreeNode nullNode) {
53         if (node == null)
54             q.add(nullNode);
55         else
56             q.add(node);
57     }
58 }

A Wrong Implementation of Enqueue

1 if (tl.left!=null || tl.right!=null) {
2     enqueue(tl.left, ql, nullNode);
3     enqueue(tl.right, ql, nullNode);
4 }
5                 
6 if (tr.left!=null || tr.right!=null) {
7     enqueue(tr.right, qr, nullNode);
8     enqueue(tr.left, qr, nullNode);
9 }

Attention:

To check whether two trees are symmetric, use the helper function checkSymmetric() alone.