力扣 – 剑指 Offer 27. 二叉树的镜像(Force buckle – Sword finger offer 27. Mirror image of binary tree)

题目

剑指 Offer 27. 二叉树的镜像

思路1(递归)

  • 我们可以使用深度优先搜索,先递归到链表的末尾,然后从末尾开始两两交换。就相当于后续遍历而已
  • 记得要先保存下来node.right节点,因为我们在递归完左边才递归右边,而递归完左边的时候,直接把node.right的指向修改了,如果事先不保存node.right节点的话,在递归右边传入的节点是错误的节点,因此得不到正确的答案

代码

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        return dfs(root);
    }

    public TreeNode dfs(TreeNode node) {
        // 为空说明到底了
        if (node == null) {
            return null;
        }

        // 先记录right节点
        TreeNode right = node.right;

        // 分别递归左边和右边,将 left 和 right 的指针互相交换
        node.right = mirrorTree(node.left);
        node.left = mirrorTree(right);

        return node;
    }
}

复杂度分析

  • 时间复杂度:\(O(N)\),遍历一遍树的每个节点要花费\(O(N)\)的时间复杂度
  • 空间复杂度:\(O(N)\),最坏情况下是一条链表,因此递归需要\(O(N)\)的栈空间

思路2(迭代)

  • 使用队列(也可以使用栈,差不多一样)进行存储节点,就是数的层序遍历
  • 节点是按顺序入队,因此我们需要做的就是将队头元素出队,然后将他的两个子节点入队,再交换两个子节点的值就可以完成一个子节点左右孩子的交换,重复所有的节点
  • 其实就是从树根到树叶将每个子节点都进行交换,最终完成了整个树的交换,形成镜像

代码

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

        // 使用队列存储节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            // 将子节点入队
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            // 交换左右两个子节点
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
        }

        return root;
    }
}

复杂度分析

  • 时间复杂度:\(O(N)\)
  • 空间复杂度:\(O(N)\),栈最多存储 \(\frac{N + 1}{2}\)个节点
————————

subject

Sword finger offer 27. Image of binary tree

Idea 1 (recursion)

  • We can use depth first search, first recurse to the end of the linked list, and then exchange from the end. It’s equivalent to subsequent traversal
  • Remember to save the node.right node first, because we only recurse to the right after recursion on the left. When recursion on the left, we directly modify the point of node.right. If we don’t save the node.right node in advance, the incoming node on the right of recursion is the wrong node, so we can’t get the correct answer

code

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        return dfs(root);
    }

    public TreeNode dfs(TreeNode node) {
        // 为空说明到底了
        if (node == null) {
            return null;
        }

        // 先记录right节点
        TreeNode right = node.right;

        // 分别递归左边和右边,将 left 和 right 的指针互相交换
        node.right = mirrorTree(node.left);
        node.left = mirrorTree(right);

        return node;
    }
}

Complexity analysis

  • Time complexity: \ (O (n) \), it takes \ (O (n) \) to traverse each node of the tree
  • Space complexity: \ (O (n) \), in the worst case, it is a linked list, so recursion requires \ (O (n) \) stack space

Idea 2 (iteration)

  • Using queues (or stacks, almost the same) for storage nodes is the sequence traversal of numbers
  • Nodes are queued in order, so what we need to do is to take the team head element out of the team, then queue its two child nodes, and then exchange the values of the two child nodes to complete the exchange of children around a child node and repeat all nodes
  • In fact, each child node is exchanged from the tree root to the leaves, and finally the exchange of the whole tree is completed to form a mirror image

code

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

        // 使用队列存储节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            // 将子节点入队
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            // 交换左右两个子节点
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
        }

        return root;
    }
}

Complexity analysis

  • Time complexity: \ (O (n) \)
  • Space complexity: \ (O (n) \), the stack can store up to \ (\ frac {n + 1} {2} \) nodes