26.翻转二叉树(重要)

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目范围在 [0, 100] 内
• -100 <= Node.val <= 100

 1 利用前序遍历
 2 class Solution {
 3         // 先序遍历--从顶向下交换
 4         public TreeNode invertTree(TreeNode root) {
 5             if (root == null) return null;
 6             // 保存右子树
 7             TreeNode rightTree = root.right;
 8             // 交换左右子树的位置
 9             root.right = invertTree(root.left);
10             root.left = invertTree(rightTree);
11             return root;
12         }
13     }
14 
15 利用中序遍历
16 class Solution {
17     public TreeNode invertTree(TreeNode root) {
18             if (root == null) return null;
19             invertTree(root.left); // 递归找到左节点
20             TreeNode rightNode= root.right; // 保存右节点
21             root.right = root.left;
22             root.left = rightNode;
23             // 递归找到右节点 继续交换 : 因为此时左右节点已经交换了,所以此时的右节点为root.left
24             invertTree(root.left); 
25     }
26 }
27 
28 利用后序遍历
29  class Solution {
30         public TreeNode invertTree(TreeNode root) {
31             // 后序遍历-- 从下向上交换
32             if (root == null) return null;
33             TreeNode leftNode = invertTree(root.left);
34             TreeNode rightNode = invertTree(root.right);
35             root.right = leftNode;
36             root.left = rightNode;
37             return root;
38         }
39     }
40 
41 利用层次遍历
42    class Solution {
43         public TreeNode invertTree(TreeNode root) {
44             // 层次遍历--直接左右交换即可
45             if (root == null) return null;
46             Queue queue = new LinkedList<>();
47             queue.offer(root);
48             while (!queue.isEmpty()){
49                 TreeNode node = queue.poll();
50                 TreeNode rightTree = node.right;
51                 node.right = node.left;
52                 node.left = rightTree;
53                 if (node.left != null){
54                     queue.offer(node.left);
55                 }
56                 if (node.right != null){
57                     queue.offer(node.right);
58                 }
59             }
60             return root;
61         }
62     }