Leetcode: Symmetric tree
The task is to determine if a tree is symmetric, meaning mirrored along the root
node. The usual tree structure is given in form of a TreeNode
.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
A symmetric tree looks like this:
Note that the 3 and 4 are flipped in the left vs. right branch.
1
/ \
2 2
/ \ / \
3 4 4 3
An asymmetric tree looks like this:
Note that the 3 would need to be on the other side of
either branch to make this tree symmetric.
1
/ \
2 2
/ /
3 3
None
while the right child is not and vice versa. If both children are None
, return True
and do not proceed because this means we reached a leaf node.
The recursive solution looks like this.
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if root is None:
return True
return self.inner(root.left, root.right)
def inner(self, left, right) -> bool:
if left is None and right is None:
return True
if left is None and right is not None:
return False
if left is not None and right is None:
return False
l = self.inner(left.left, right.right)
r = self.inner(left.right, right.left)
return left.val == right.val and l and r
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if root is None:
return True
# Create stack and initialize with immediate successors
stack = [(root.left, root.right)]
while len(stack) > 0:
n = stack[0]
stack = stack[1:]
if n[0] is None and n[1] is not None:
return False
if n[0] is not None and n[1] is None:
return False
if n[0] is None and n[1] is None:
continue
if n[0].val != n[1].val:
return False
stack.append((n[0].left, n[1].right))
stack.append((n[0].right, n[1].left))
return True
if __name__ == '__main__':
s = Solution().isSymmetric
print(s(TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(2, TreeNode(4), TreeNode(3)))), True)