题目

剑指 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}\)个节点
11-24 11:49