226.翻转二叉树

226.翻转二叉树

题目地址：力扣

翻转一棵二叉树。

思路：

我们之前介绍的都是各种方式遍历二叉树，这次要翻转了，感觉还是有点懵逼。

这得怎么翻转呢？

如果要从整个树来看，翻转还真的挺复杂，整个树以中间分割线进行翻转，如图：

可以发现想要翻转它，其实就把每一个节点的左右孩子交换一下就可以了。

关键在于遍历顺序，前中后序应该选哪一种遍历顺序？ （一些同学这道题都过了，但是不知道自己用的是什么顺序）

遍历的过程中去翻转每一个节点的左右孩子就可以达到整体翻转的效果。

**注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果**

**这道题目使用前序遍历和后序遍历都可以，唯独中序遍历不行，因为中序遍历会把某些节点的左右孩子翻转了两次！**

那么层序遍历可以不可以呢？**依然可以的！只要把每一个节点的左右孩子翻转一下的遍历方式都是可以的！**

递归法：

1. 确定递归函数的参数和返回值

参数就是要传入节点的指针，不需要其他参数了，通常此时定下来主要参数，如果在写递归的逻辑中发现还需要其他参数的时候，随时补充。

返回值的话其实也不需要，但是题目中给出的要返回root节点的指针，可以直接使用题目定义好的函数，所以就函数的返回类型为`TreeNode`。

```
TreeNode invertTree(TreeNode root)
```

2. 确定终止条件

当前节点为空的时候，就返回

```
if (root == NULL) return root;
```

3. 确定单层递归的逻辑

因为是先前序遍历，所以先进行交换左右孩子节点，然后反转左子树，反转右子树。

```
swap(root);
invertTree(root.left);
invertTree(root.right);
```

基于这递归三步法，代码基本写完，Java代码如下：

```JAVA
class Solution {
  public TreeNode invertTree(TreeNode root) {
      if (root == NULL){return root;}
      swap(root);                           // 中
      invertTree(root.left);         // 左
      invertTree(root.right);        // 右
      return root;
    }

    public void swap(TreeNode root){

        TreeNode tmp = root.left;

        root.left = root.right;

        root.right = tmp;

    }
};
```

迭代法:

深度优先遍历

```

//BFS
class Solution {
    public TreeNode invertTree(TreeNode root) {
       if (root == null) {return null;}
       ArrayDeque<TreeNode> deque = new ArrayDeque<>();
       deque.offer(root);
       while (!deque.isEmpty()) {
          int size = deque.size();
          while (size-- > 0) {
           TreeNode node = deque.poll();
           swap(node);
           if (node.left != null) {deque.offer(node.left);}
             if (node.right != null) {deque.offer(node.right);}
          }
       }
       return root;
    }

    public void swap(TreeNode root) {
       TreeNode temp = root.left;
       root.left = root.right;
       root.right = temp;
    }
}
```