226. 翻转二叉树 

不同的二叉树搜索方法不同的做法

1 深度优先搜索

迭代和递归

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        # 深度优先搜索 用stack 前序遍历
        if not root:
            return root
        stack = [root]

        # 中左右
        while stack:
            cur  = stack.pop()
            cur.left, cur.right = cur.right, cur.left
            if cur.right:
                stack.append(cur.right)
            if cur.left:
                stack.append(cur.left)
        return root

# class Solution(object):
#     def invertTree(self, root):
          # 递归
          #递归的中序遍历是不行的
#         if not root:
#             return 
#         root.left, root.right = root.right, root.left
#         self.invertTree(root.left)
#         self.invertTree(root.right)
#         return root

2广度优先搜索

层序遍历

# 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
from collections import deque
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        # 使用层序遍历 用deque
        if not root:
            return root
        que = deque([root])
        while que:
            for _ in range(len(que)):
                cur = que.popleft()
                cur.left, cur.right = cur.right, cur.left
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
        return root