Franklin

Symmetric Tree

TreeRecursionDFSBFS
https://leetcode.com/problems/symmetric-tree

# Definition for a Binary Tree Node

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
1
2
3
4
5

# Solution

Both solutions take linear time and space.

# Recursion

Two trees are mirrors of each other if:

  • the two roots have the same value
  • the right subtree of each tree is a mirror reflection of the left subtree of the other tree
def mirror(self, t1: TreeNode, t2: TreeNode) -> bool:
    if not t1 and not t2:
        return True
    elif not t1 or not t2:
        return False
    else:
        return t1.val == t2.val\
        and self.mirror(t1.left, t2.right)\
        and self.mirror(t1.right, t2.left)

def isSymmetric(self, root: TreeNode) -> bool:
    return self.mirror(root, root)
1
2
3
4
5
6
7
8
9
10
11
12

# Iteration

The following code follows a BFS order to traverse the binary tree, but queue.pop() (DFS order) also works.

def isSymmetric(self, root: TreeNode) -> bool:
    queue = []
    queue.append(root)
    queue.append(root)
    while queue:
        t1 = queue.pop(0)
        t2 = queue.pop(0)
        if not t1 and not t2:
            continue
        elif not t1 or not t2:
            return False
        elif t1.val != t2.val:
            return False
        else:
            queue.append(t1.left)
            queue.append(t2.right)
            queue.append(t1.right)
            queue.append(t2.left)
    return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Target Sum