LC 226.翻转二叉树 ⭐⭐⭐⭐

[HealUP]

226. 翻转二叉树

解决方案包括递归法和非递归法：

• 递归法 实现前中后序遍历
• 非递归法即迭代法，包括：
  • 深度优先搜索 DFS 使用栈模拟 实现前中后序遍历 => 基于栈的深搜其实还不好写统一的前中后序遍历，但是有统一的写法，一刷的时候，由于比较赶，先不写。先掌握递归的写法🐛
  • 广度优先搜索 BFS 使用队列模拟 实现层序遍历

法一：递归法（这道题目使用前序遍历和后序遍历都可以，唯独中序遍历不方便，因为中序遍历会把某些节点的左右孩子翻转了两次）

首先确定三要素：

• 确定递归函数的参数和返回值
• 确定终止条件
• 确定单层递归的逻辑

class Solution {
    //递归函数
    public TreeNode invertTree(TreeNode root) {
        //递归法
        if (root == null) {
            return root;
        }
        //直接交换，使用前序遍历
        swapChildren(root);//中
        invertTree(root.left);//左节点放入  反转的时候将左节点的左右子节点翻转
        invertTree(root.right);//右节点放入 
        return root;
    }
    //交换左右节点
    public void swapChildren (TreeNode root) {
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

法二：迭代法—层序遍历

思路：层序遍历，每一层分别反转

class Solution {
    public TreeNode invertTree(TreeNode root) {
       //层序遍历 每一层的节点分别翻转
       if (root == null) {return null;}
       Queue<TreeNode> que = new LinkedList<>();
       que.offer(root);
       while (!que.isEmpty()) {
           int len = que.size();
           for (int i = 0; i < len; i++) {
               TreeNode node = que.poll();
               swapChildren(node);
               if (node.left != null) que.offer(node.left);
               if (node.right != null) que.offer(node.right);
           }
       }
       return root;
    }

    //交换左右节点
    public void swapChildren (TreeNode root) {
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}