[每日一题] 第二十五题:二叉树的镜像

题目描述

请完成一个函数,输入一个二叉树,该函数输出它的镜像。

例如输入:

     4
   /
  2     7
 / \   /
1   3 6   9

镜像输出:

     4
   /
  7     2
 / \   /
9   6 3   1

示例 1:

输入:root = [4,2,7,1,3,6,9]
输出:[4,7,2,9,6,3,1]

题解

二叉树像定义:对于二叉树中任意节点 root,设其左/右子节点分别为 left,right;则在二叉树的镜像中的对应 root 节点,其左/右节点分别为 right,left。

[每日一题] 第二十五题:二叉树的镜像

方法一:递归法

  • 根据二叉树镜像的定义,考虑递归遍历(dfs)二叉树,交换每个节点的左/右子节点,即可生成二叉树的镜像。

递归解析:

  1. 终止条件:当节点 root 为空时(即越过叶节点),则返回 null;

  2. 递推工作

    1. 初始化节点 tmp,用于暂存 root 的左子节点;
    2. 开启递归 右子节点 mirrorTree(root.right),并将返回值作为 root 的 左子节点
    3. 开启递归 左子节点 mirrorTree(tmp),并将返回值作为 root 的 右子节点
  3. 返回值:返回当前节点 root;

Q:为何需要暂存 root 的左子节点?
A:在递归右子节点 root.left = mirrorTree(root.right); 执行完毕后,root.left 的值已经发生改变,此时递归左子节点 mirrorTree(root.left) 则会出问题。

代码

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

复杂度分析

  • 时间复杂度 O(N) :其中 N 为二叉树的节点数量,建立二叉树镜像需要遍历所有节点,占用 O(N) 的时间。
  • 空间复杂度 O(N) :最差情况下(当二叉树退化成链表),递归时系统需要 O(N) 大小的栈空间。

题解来源

作者:jyd
链接:leetcode-cn.com/problems/er-cha-sh...
来源:力扣(LeetCode)

方法二:辅助栈(或队列)

  • 利用栈或队列遍历树的所有节点 node,并交换每个 node 的左/右子节点。

算法流程

  1. 特例处理:当 root 为空时,直接返回 null。

  2. 初始化:栈(或队列),本文用栈,并加入根节点 root。

  3. 循环交换:当栈 stack 为空时跳出:

    1. 出栈:记为 node;
    2. 添加左/右子节点:将 node 的左/右子节点入栈;
    3. 交换:交换 node 的左/右子节点。
  4. 返回值:返回根节点 root。

代码

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        Stack<TreeNode> stack = new Stack<>() {{ add(root); }};
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if(node.left != null) stack.add(node.left);
            if(node.right != null) stack.add(node.right);
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        return root;
    }
}

复杂度分析

  • 时间复杂度 O(N) :其中 N 为二叉树节点的数量,建立二叉镜像树需要遍历树的所有节点,占用 O(N) 的时间。
  • 空间复杂度 O(N) :最差情况下,当为满二叉树,栈 stack 最多同时存储 N/2 个节点,占用 O(N) 的额外空间。

题解来源

作者:jyd
链接:leetcode-cn.com/problems/er-cha-sh...
来源:力扣(LeetCode)

题目来源

来源:力扣(LeetCode)
链接:leetcode-cn.com/problems/er-cha-sh...

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!