LeetCode OJ：Symmetric Tree（对称的树）

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:

判断一颗树是否对称，首先用递归的方法当然比较容易解决：

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     bool isSymmetric(TreeNode* root) {
13         if(root == NULL)
14             return true;
15         if(!root->left && !root->right)
16             return true;
17         if(root->left && !root->right || !root->left && root->right)
18             return false;
19         return checkSymmetric(root->left, root->right);
20     }
21 
22     bool checkSymmetric(TreeNode * left, TreeNode * right)
23     {
24         if(!left && !right)
25             return true;
26         if(!left && right || left && !right)
27             return false;
28         if(left->val != right->val)
29             return false;
30         return checkSymmetric(left->left, right->right) && checkSymmetric(left->right, right->left);
31     }
32 };

题目还要求用非递归的方式来实现，制造两个队列就可以实现了：

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     bool isSymmetric(TreeNode* root) {
13         queue<TreeNode *> q1;
14         queue<TreeNode *> q2;
15         if(root == NULL) return true;
16         if(!root->left && !root->right) return true;
17         if(root->left && !root->right || !root->left && root->right) return false;//val
18         q1.push(root->left);
19         q2.push(root->right);
20         TreeNode * tmpLeft, *tmpRight;
21         while(!q1.empty() && !q2.empty()){
22             tmpLeft = q1.front();
23             tmpRight = q2.front();
24             q1.pop(), q2.pop();
25             if(!tmpLeft && !tmpRight)
26                 continue;
27             if(!tmpLeft && tmpRight || tmpLeft && !tmpRight)
28                 return false;
29             if(tmpLeft->val != tmpRight->val)
30                 return false;
31             q1.push(tmpLeft->left);
32             q1.push(tmpLeft->right);
33             q2.push(tmpRight->right);
34             q2.push(tmpRight->left);
35         }
36         return q1.empty() && q2.empty();
37     }
38 };

java的递归版本如下所示：

 1 public class Solution {
 2     public boolean isSymmetric(TreeNode root) {
 3         if(root == null)
 4             return true;
 5         if(root.left == null && root.right == null)
 6             return true;
 7         if(root.left != null && root.right != null)
 8             return checkSymmetric(root.left, root.right);
 9         return false;
10     }
11     
12     public boolean checkSymmetric(TreeNode leftNode, TreeNode rightNode){
13         if(leftNode == null && rightNode == null)
14             return true;
15         if(leftNode != null && rightNode != null){
16             if(leftNode.val == rightNode.val){
17                 return checkSymmetric(leftNode.left, rightNode.right) && 
18                        checkSymmetric(leftNode.right, rightNode.left);
19             }
20             else 
21                 return false;
22         }
23         return false;
24     }
25 }

下面是迭代版本，和上面的基本上一样：

public class Solution {
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> q1 = new LinkedList<TreeNode>();
        Queue<TreeNode> q2 = new LinkedList<TreeNode>();
        TreeNode p1, p2;
        if(root == null)
            return true;
        q1.add(root.left);
        q2.add(root.right);
        while(!q1.isEmpty() && !q2.isEmpty()){
            p1 = q1.poll();
            p2 = q2.poll();
            if(p1 == null && p2 == null)
                continue;
            if(p1 != null && p2 != null){
                if(p1.val == p2.val){
                    q1.add(p1.left);
                    q1.add(p1.right);
                    q2.add(p2.right);
                    q2.add(p2.left);
                }else
                    return false;
            }else
                return false;
        }
        return true;
    }
}