# Symmetric Tree

Nov 14, 2017

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

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


But the following [1,2,2,null,3,null,3] is not:

    1
/ \
2   2
\   \
3    3


def isSymmetric1(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root is None:
return True
else:
return self.isSymmetricRec(root.left,root.right)

def isSymmetricRec(self,left,right):
"""
:type left: TreeNode
:type right: TreeNode
:rtype: bool
"""
if left is None and right is None:
return True
elif left is not None and right is not None:
return left.val == right.val \
and self.isSymmetricRec(left.left,right.right) \
and self.isSymmetricRec(left.right,right.left)
else:
return False


def isSymmetricBFS(self,root):
"""
:type root:TreeNode
:rtype: bool
"""
if root is None:
return True

leftqueue = Queue()
rightqueue = Queue()

leftqueue.put(root.left)
rightqueue.put(root.right)

while not leftqueue.empty():
left = leftqueue.get()
right = rightqueue.get()
if left is None and right is None:
continue
elif left is not None and right is not None:
if left.val != right.val:
return False
leftqueue.put(left.left)
leftqueue.put(left.right)
rightqueue.put(right.right)
rightqueue.put(right.left)
else:
return False
return True


bool isSymmetric(TreeNode *root) {
if (!root) return true;
return helper(root->left, root->right);
}

bool helper(TreeNode* p, TreeNode* q) {
if (!p && !q) {
return true;
} else if (!p || !q) {
return false;
}

if (p->val != q->val) {
return false;
}

return helper(p->left,q->right) && helper(p->right, q->left);
}

bool isSymmetric(TreeNode *root) {
TreeNode *left, *right;
if (!root)
return true;

queue<TreeNode*> q1, q2;
q1.push(root->left);
q2.push(root->right);
while (!q1.empty() && !q2.empty()){
left = q1.front();
q1.pop();
right = q2.front();
q2.pop();
if (NULL == left && NULL == right)
continue;
if (NULL == left || NULL == right)
return false;
if (left->val != right->val)
return false;
q1.push(left->left);
q1.push(left->right);
q2.push(right->right);
q2.push(right->left);
}
return true;
}

LeetCodeLeetCodeTree

Best Time to Buy and Sell Stock

Balanced Binary Tree