38. 翻转二叉树

 LCR 144. 翻转二叉树

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

示例 1：

输入：root = [5,7,9,8,3,2,4]
输出：[5,9,7,4,2,3,8] 

方法一：递归

 递归到最底层交换左右两个结点 并返回子树的根结点。

class Solution {
    public TreeNode flipTree(TreeNode root) {
        if(root == null) return null;
        // flipTree 返回交换后的根节点root
        TreeNode left_root = flipTree(root.right);
        TreeNode right_root = flipTree(root.left);
        root.left = left_root;
        root.right = right_root;
        return root;
    }
}

 

方法二：辅助队列——层序遍历

先交换root左右子树，再将左右root加入队列

class Solution {
    public TreeNode flipTree(TreeNode root) {
        if(root == null) return null;

        // Queue是 Java 的抽象接口，不能直接new Queue()，必须使用具体实现类（如LinkedList）。
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            swap(node);
            if(node.left != null)queue.offer(node.left);
            if(node.right != null)queue.offer(node.right);
        }
        return root;
    }
    // 直接传TreeNode a/b交换的是方法内的局部变量，无法真正交换节点的左右子树swap(TreeNode a, TreeNode b)
    // 一个为拿着复印件去找地址下的东西修改，所以能修改成功；一个为直接修改复印件
    public void swap(TreeNode root){
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }
}

 

注意！！！

Queue是 Java 的抽象接口，不能直接new Queue()，必须使用具体实现类（如LinkedList）

Queue<TreeNode> queue = new LinkedList<TreeNode>();

Java是值传递，直接传TreeNode a/b交换的是方法内的局部变量，无法真正交换节点的左右子树swap(TreeNode a, TreeNode b)

一个为拿着复印件去找地址下的东西修改，所以能修改成功；一个为直接修改复印件