LeetCode OJ：Same Tree（相同的树）

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

判断两个树是否相同，起是用递归很好解决，但是我一开始居然想使用前序加中序遍历来唯一确定一棵树：

 1 class Solution {
 2 public:
 3     bool isSameTree(TreeNode* p, TreeNode* q) {
 4         vector<int>res1;
 5         vector<int>res2;
 6         if(p == NULL && q == NULL)
 7             return true;
 8         else if(p == NULL || q == NULL)
 9             return false;
10         preorderTraversal(p, res1);
11         preorderTraversal(q, res2);
12         bool ans1 = res1 == res2;
13         res1.clear(), res2.clear();
14         infixTraversal(p, res1);
15         infixTraversal(q, res2);
16         bool ans2 = res1 == res2;
17         return res1 && res2;
18 
19     }
20     void preorderTraversal(TreeNode * p, vector<int> & res)
21     {
22         if(p == NULL) return;
23         res.push_back(p->val);
24         preorderTraversal(p->left, res);
25         preorderTraversal(p->right, res);
26     }
27     void infixTraversal(TreeNode * p, vector<int> & res)
28     {
29         if(p == NULL) return;
30         infixTraversal(p->left, res);
31         res.push_back(p->val);
32         infixTraversal(p->right, res);
33     }
34 };

然而并不可行，只能使用下面这一种方法：

 1 class Solution {
 2 public:
 3     bool isSameTree(TreeNode* p, TreeNode* q) {
 4         if(!p && !q)
 5             return true;
 6         else if(!p && q)
 7             return false;
 8         else if(p && !q)
 9             return false;
10         else{
11             if(p->val != q->val)
12                 return false;
13             else
14                 return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
15         }
16     }
17 };

当然也可以采用迭代的方式来完成：

 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 isSameTree(TreeNode* p, TreeNode* q) {
13         queue<TreeNode *> pQueue;
14         queue<TreeNode *> qQueue;
15         pQueue.push(p); //这里只能用队列而不能用栈，因为单向链表的性质决定
16         qQueue.push(q);
17         while(!pQueue.empty() && !qQueue.empty()){
18             TreeNode * pTmp = pQueue.front();
19             TreeNode * qTmp = qQueue.front();
20             pQueue.pop(), qQueue.pop();
21             if(!pTmp && !qTmp)
22                 continue;
23             else if(pTmp && !qTmp || !pTmp && qTmp || pTmp->val != qTmp->val)
24                 return false;
25             else{
26                 pQueue.push(pTmp->left);
27                 pQueue.push(pTmp->right);
28                 qQueue.push(qTmp->left);
29                 qQueue.push(qTmp->right);
30             }
31         }
32         return pQueue.empty() && qQueue.empty();
33     }
34 };

下面是java代码：

递归的：

 1 /**
 2  * Definition for a binary tree node.
 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 isSameTree(TreeNode p, TreeNode q) {
12         if(p == null && q == null)
13             return true;
14         else if(p == null)
15             return false;
16         else if(q == null)
17             return false;
18         else{
19             if(p.val == q.val){
20                 return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
21             }else
22                 return false;
23         }
24     }
25 }

迭代版：

 1 public class Solution {
 2     public boolean isSameTree(TreeNode p, TreeNode q) {
 3         Queue<TreeNode> queueP = new LinkedList<TreeNode>();
 4         Queue<TreeNode> queueQ = new LinkedList<TreeNode>();
 5         TreeNode p1, p2;
 6         queueP.add(p);
 7         queueQ.add(q);
 8         while(!queueP.isEmpty() && !queueQ.isEmpty()){
 9             p1 = queueP.poll();
10             p2 = queueQ.poll();
11             if(p1 == null && p2 != null || 
12                p1 != null && p2 == null)
13                return false;
14             if(p1 == null && p2 == null)
15                 continue;
16             if(p1.val == p2.val){
17                 queueP.add(p1.left);
18                 queueP.add(p1.right);
19                 queueQ.add(p2.left);
20                 queueQ.add(p2.right);
21             }else return false;
22         }
23         if(queueP.isEmpty() && queueQ.isEmpty())
24             return true;
25         return false;
26     }
27 }