Symmetric Tree@leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

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.

这题递归法比较简单，几行代码的事情。但是我在oj的时候老是不通过，逻辑很简单，而且我确定是对的，后来自己跑到emacs上面调试，发现有segmentation fault，原来是我做判断的时候的一句话

if(l->val==r->val&&!l&&!r)

这种情况下，l or r 有可能是null，那么就没有l->val or r->val, 就会出现问题，这样把空判断提前就可以了，细节，但一定要注意！

这题难的是iterative的解法，基本做法是BFS，一层一层看是否对称，然后用两个queue来存储结点。

	/**
	* Definition for binary tree
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	bool symTree(TreeNode *l, TreeNode *r)
	{
	if(l==NULL&&r==NULL) return true;
	bool res=false;
	if(l!=NULL&&r!=NULL&&l->val==r->val)
	{
	res=symTree(l->left, r->right)&&symTree(l->right, r->left);
	}
	return res;
	}
	bool isSymmetric(TreeNode *root) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	if(root==NULL) return true;
	return symTree(root->left, root->right);
	}
	};

view raw Symmetric Tree@recursion hosted with ❤ by GitHub

	/**
	* Definition for binary tree
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	bool isSymmetric(TreeNode *root) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	if(root==NULL) return true;
	queue<TreeNode*> q1;
	queue<TreeNode*> q2;
	q1.push(root->left);
	q2.push(root->right);
	while(!q1.empty()&&!q2.empty())
	{
	TreeNode *t1=q1.front();
	TreeNode *t2=q2.front();
	q1.pop();
	q2.pop();
	if((t1!=NULL&&t2==NULL)||(t1==NULL&&t2!=NULL))
	return false;
	if(t1!=NULL&&t2!=NULL)
	{
	if(t1->val!=t2->val)
	return false;
	q1.push(t1->left);
	q1.push(t1->right);
	q2.push(t2->right);
	q2.push(t2->left);
	}
	}
	return true;
	}
	};

view raw Symmetric Tree@iterate hosted with ❤ by GitHub