题目描述：翻转一棵二叉树。

示例：

输入：

  1.  4

/ \ 2 7 / \ / \ 1 3 6 9

输出：

  1.  4

/ \ 7 2 / \ / \ 9 6 3 1

  • 题解：

仔细审题得话，可以发现无论怎么操作，始终都是要遍历每一个节点，也就是说复杂度为 O(n)。
二叉树的遍历方法有两类：

  • 深度优先遍历 - DFS（Depth First Search）
  • 广度优先遍历 - BFS（Breadth First Search）

引用[1]内有话说得很形象：沿着一条路进行深入探索，发现走到头再寻找其他出路得方式就叫深度优先遍历，这种向前回溯的方式很符合栈的先入后出特性，相互结合即可实现深度优先遍历算法。
层层遍历的方式与队列先进先出的特性结合起来可实现广度优先算法，每一层遍历的方式均与上一层相同，是一个迭代的过程。

  1. 深度遍历该二叉树，然后交换其左右节点 ```python

    Definition for a binary tree node.

    class TreeNode:

    def init(self, x):

    self.val = x

    self.left = None

    self.right = None

class Solution: def invertTree(self, root: TreeNode) -> TreeNode: if root is None: return root

  1.     right = self.invertTree(root.right)
  2.     left = self.invertTree(root.left)
  3.     root.left, root.right = right, left
  4.     return root
  2. 2. 采用广度优先的方式来遍历该二叉树，并逐个交换左右节点
  3. ```python
  4. # Definition for a binary tree node.
  5. # class TreeNode:
  6. #     def __init__(self, x):
  7. #         self.val = x
  8. #         self.left = None
  9. #         self.right = None
  11. class Solution:
  12.     def invertTree(self, root: TreeNode) -> TreeNode:
  13.         if root is None:
  14.             return root
  16.         queue = [root]
  17.         while queue:
  18.             cur_node = queue.pop(0)
  19.             cur_node.left, cur_node.right = cur_node.right, cur_node.left
  20.             if cur_node.left is not None:
  21.                 queue.append(cur_node.left)
  22.             if cur_node.right is not None:
  23.                 queue.append(cur_node.right)
  25.         return root

引用：
[1]. 漫画：深度优先遍历 和 广度优先遍历