LeetCode Q101: 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:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Solution 1: Recursive solution.
Similar to question of check whether two trees are identical. Here, the difference is the order we access the left and right sub-trees of two trees.

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	bool helper(TreeNode* tr1, TreeNode* tr2){
	if(tr1==NULL&&tr2==NULL)
	return true;
	if((tr1==NULL&&tr2!=NULL) || (tr1!=NULL&&tr2==NULL))
	return false;
	if(tr1->val!=tr2->val)
	return false;
	bool r0=helper(tr1->left, tr2->right);
	bool r1=helper(tr1->right, tr2->left);
	return r0&&r1;
	}
	bool isSymmetric(TreeNode* root) {
	if(root==NULL)
	return true;
	return helper(root->left, root->right);
	}
	};

view raw Q101SymmetricTrees.cpp hosted with ❤ by GitHub

Solution 2: Iterative solution.

	class Solution {
	public:
	bool isSymmetric(TreeNode* root) {
	if(root==NULL)
	return true;
	queue<TreeNode*> ltr;
	queue<TreeNode*> rtr;
	ltr.push(root->left);
	rtr.push(root->right);
	while(!ltr.empty()&&!rtr.empty()){
	TreeNode* ltop=ltr.front();
	TreeNode* rtop=rtr.front();
	ltr.pop(); rtr.pop();
	if(ltop==NULL&&rtop==NULL)
	continue;
	if((ltop==NULL&&rtop!=NULL) || (ltop!=NULL&&rtop==NULL))
	return false;
	if(ltop->val!=rtop->val)
	return false;
	ltr.push(ltop->left); ltr.push(ltop->right);
	rtr.push(rtop->right); rtr.push(rtop->left);
	}
	return true;
	}
	};

view raw Q101-2.cpp hosted with ❤ by GitHub