博客

226. 翻转二叉树

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

简单难度。这道题与

剑指 Offer 27. 二叉树的镜像

属于同一道题。使用后续递归交换左右子节点的位置的方式是最简单的。

public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode left = invertTree(root.left);
    TreeNode right = invertTree(root.right);
    //交换左右子节点的位置
    root.left = right;
    root.right = left;
    return root;
}

另一种方式是迭代法。迭代就层序，使用一个辅助队列，将对当前节点的子节点交换然后将子节点存入队列即可。

public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    LinkedList<TreeNode> queue = new LinkedList<>();
    //根节点存入队列
    queue.addLast(root);
    while (!queue.isEmpty()) {
        TreeNode t = queue.removeFirst();
        //交换子节点
        TreeNode right = t.right;
        t.right = t.left;
        t.left = right;
        //子节点存入队列
        if (t.left != null) {
            queue.addLast(t.left);
        }
        if (t.right != null) {
            queue.addLast(t.right);
        }
    }
    return root;
}