翻转二叉树

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

解题思路

方法一

递归法

前序遍历和后序遍历都行，这里采用前序遍历

代码

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null) return root;
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        root.left = invertTree(root.left);
        root.right = invertTree(root.right);
        return root;
    }
}

方法二

迭代法（层次遍历）

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {return root;}
        LinkedList<TreeNode> list = new LinkedList<>();
        list.addLast(root);
        while (!list.isEmpty()) {
            int size = list.size();
            for(int i = 0 ; i < size ;i++){
                TreeNode node = list.removeFirst();
                swap(node);
                if (node.left != null) {list.addLast(node.left);}
                if (node.right != null) {list.addLast(node.right);}
            }
        }
        return root;
    }

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