leetcode1-226. Invert Binary Tree

BSF = Breadth-First-Search
DSF = Depth-First-Search

1. problem

given an array that can be represent as a tree.
swap left and right node, and return whole array(tree). for example:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

2. init

# 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
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:

3. thought

1. if node is empty, return  
2. assume it's balance tree,   
3. if left/right node has child, recursive  
4. else swap  

4. trouble

• NoneType’ object has no attribute ‘left’
  fix it by check if input == []

  if root is None:
      return root

  5.final solution

  Runtime 77 ms Beats 6.10% Memory 14 MB Beats 12.42%

  # 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
  class Solution:
      def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
          if root is None:
              return root
          if root.left is None and root.right is None: 
              return root
          else: 
              root.left  = self.invertTree(root.left)
              root.right = self.invertTree(root.right)
              temp = root.left
              root.left = root.right
              root.right = temp
              return root