Code & Fun

第48天。

今天的题目是Symmetric Tree:

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
3
4
5
    1
/ \
2 2
/ \ / \
3 4 4 3

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

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

刚看的时候还有点懵,要怎么递归的去求解这种问题呢,要比较的两个节点隔得有点远啊。后来是上课时突然想到对称其实和根节点的左子树和右子树有关,我们把他当成两个树来求解就好了,递归时需要两个TreeNode:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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

然后是迭代解,这里是用层次遍历去做的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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

然后是在dicuss中看到的c++解法,思路其实是一样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
}

本文首发于Code & Fun