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.
confused what "{1,#,2,3}" means?
方法一：递归实现
1 /** 2 * Definition for binary tree 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 bool canBeSymmetric(TreeNode *p, TreeNode *q) 11 { 12 if(p==NULL && q==NULL) 13 return true; 14 if((p==NULL && q!=NULL) || (p!=NULL && q==NULL)) 15 return false; 16 17 if(p->val != q->val) 18 return false; 19 bool b1 = canBeSymmetric(p->left, q->right); //若二叉树p和二叉树q对称，则 p 的左子树和 q 的右子树对称 20 if(b1==false) 21 return false; 22 bool b2 = canBeSymmetric(p->right, q->left); //若二叉树p和二叉树q对称，则 p 的右子树和 q 的左子树对称 23 24 return b2; 25 26 } 27 28 class Solution { 29 public: 30 bool isSymmetric(TreeNode *root) { 31 32 if(root==NULL) 33 return true; 34 35 return canBeSymmetric(root->left, root->right); 36 } 37 };
方法二：迭代实现
1 /** 2 * Definition for binary tree 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 vector<int> PreOrderTraverse(TreeNode *p) //按根左右的顺序遍历二叉树，迭代实现 11 { 12 vector<int> result; 13 stack<TreeNode*> st; 14 15 while(p || !st.empty()) 16 { 17 if(p) 18 { 19 result.push_back(p->val); 20 st.push(p); 21 p = p->left; 22 } 23 else 24 { 25 result.push_back(0); //用0表示空树 26 p = st.top(); 27 st.pop(); 28 p = p->right; 29 } 30 } 31 result.push_back(0); 32 return result; 33 } 34 35 vector<int> ReversePreOrderTraverse(TreeNode *p) //按根右左的顺序遍历二叉树，迭代实现 36 { 37 vector<int> result; 38 stack<TreeNode*> st; 39 40 while(p || !st.empty()) 41 { 42 if(p) 43 { 44 result.push_back(p->val); 45 st.push(p); 46 p = p->right; 47 } 48 else 49 { 50 result.push_back(0); //用0表示空树 51 p = st.top(); 52 st.pop(); 53 p = p->left; 54 } 55 } 56 result.push_back(0); 57 return result; 58 } 59 60 61 class Solution { 62 public: 63 bool isSymmetric(TreeNode *root) { 64 65 if(root==NULL) 66 return true; 67 68 vector<int> ivec1 = PreOrderTraverse(root->left); 69 vector<int> ivec2 = ReversePreOrderTraverse(root->right); 70 71 return ivec1==ivec2; 72 } 73 };
注：
发现对于两棵完全相同的二叉树，用"#"(方法二中是用整数0，也可以用其他的代替)代替空树，他们的先序遍历序列是完全相同的，
反之也成立，即若两颗二叉树的先序遍历序列（用"#"代替空树）完全相同，那么这两颗二叉树也必然相同。
然而这一事实对于用中序遍历序列则不成立，也就是说若两颗二叉树的中序遍历序列（用"#"代替空树）完全相同，这两颗二叉树不一定相同。举例如下：
2 / 的中序遍历序列（左根右）为： #3#2# 先序遍历序列（根左右）为： 23### 后序遍历序列（左右根）为： ##3#2 3
不同 相同 不同 不同
3 \ 的中序遍历序列（左根右）为： #3#2# 先序遍历序列（根左右）为： 3#2## 后序遍历序列（左右根）为： ###23 2
这两颗树不同，但他们对应的中序遍历序列却相同。
[LeetCode OJ] Symmetric Tree,布布扣,bubuko.com
原文：http://www.cnblogs.com/Marrybe/p/3791865.html