leetcode/101-symmetric-tree.py at master · anantkaushik/leetcode · GitHub

Name: leetcode/101-symmetric-tree.py at master · anantkaushik/leetcode · GitHub
Rating: 4.7 (8032 reviews)
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
"""
Problem Link: https://leetcode.com/problems/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 2
 / \ / \
3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
 1
 / \
 2 2
 \ \
 3 3

Note:
Bonus points if you could solve it both recursively and iteratively.
"""
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

classSolution(object):
defisSymmetric(self, root):
"""
 :type root: TreeNode
 :rtype: bool
 """
ifnotroot:
returnTrue
returnself.isMirror(root,root)

defisMirror(self,l,r):
ifnotlandnotr:
returnTrue
ifnotlornotr:
returnFalse
ifl.val==r.val:
returnself.isMirror(l.left, r.right) andself.isMirror(l.right, r.left)
returnFalse

classSolution1:
defisSymmetric(self, root: TreeNode) ->bool:
defhelper(root1, root2):
ifnotroot1ornotroot2:
returnroot1==root2

returnroot1.val==root2.valandhelper(root1.left, root2.right) andhelper(root1.right, root2.left)

returnhelper(root, root)

classSolution2:
defisSymmetric(self, root: TreeNode) ->bool:
stack= [[root, root]]

whilestack:
node1, node2=stack.pop()

ifnotnode1andnotnode2:
continue
ifnotnode1ornotnode2ornode1.val!=node2.val:
returnFalse

stack.append([node1.left, node2.right])
stack.append([node1.right, node2.left])

returnTrue