1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 27 题] “二叉树的镜像”做题记录

[剑指 Offer 第 2 版第 27 题] “二叉树的镜像”做题记录

第 27 题:操作给定的二叉树,将其变换为源二叉树的镜像

传送门:二叉树的镜像牛客网 online judge 地址

输入一个二叉树,将它变换为它的镜像。

样例:

输入树: 8 / \ 6 10 / \ / \ 5 7 9 11

[8,6,10,5,7,9,11,null,null,null,null,null,null,null,null] 输出树:

8 / \ 10 6 / \ / \ 11 9 7 5 [8,10,6,11,9,7,5,null,null,null,null,null,null,null,null]

分析:这道题的解决实际上考察了二叉树的遍历,事实上,前序遍历、后序遍历、层序遍历都是可以完成题目要求的。

思路1:递归方式:前序遍历或者后序遍历都行。

Python 代码:前序遍历

  # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None


    class Solution(object):
        def mirror(self, root):
            """
            :type root: TreeNode
            :rtype: void
            """
            # 先写递归终止条件
            if root is None:
                return root

            # 按照前序遍历的方式
            root.left, root.right = root.right, root.left
            self.mirror(root.left)
            self.mirror(root.right)

Java 代码:

  class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }
    }

    public class Solution {

        // 前序遍历和后序遍历都是可以的
        public void Mirror(TreeNode root) {
            if (root == null) {
                return;
            }
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
            Mirror(root.left);
            Mirror(root.right);
        }

        public void Mirror1(TreeNode root) {
            if (root == null) {
                return;
            }
            Mirror(root.left);
            Mirror(root.right);
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
        }
    }

Python 代码:后序遍历

  # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None


    class Solution(object):
        def mirror(self, root):
            """
            :type root: TreeNode
            :rtype: void
            """
            # 先写递归终止条件
            if root is None:
                return root

            # 按照后序遍历的方式
            self.mirror(root.left)
            self.mirror(root.right)
            root.left, root.right = root.right, root.left

Python 代码:层序遍历

  class Solution(object):
        def mirror(self, root):
            """
            :type root: TreeNode
            :rtype: void
            """
            # 先写递归终止条件
            if root is None:
                return root
            queue = [root]
            while queue:
                top = queue.pop(0)
                top.left, top.right = top.right, top.left
                if top.left:
                    queue.append(top.left)
                if top.right:
                    queue.append(top.right)
            return root

思路2:非递归方式(没有看出来是那种递归方式)。

Java 代码:

  class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public class Solution {

        // 前序遍历和后序遍历都是可以的
        public void Mirror(TreeNode root) {
            if (root == null) {
                return;
            }
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
            Mirror(root.left);
            Mirror(root.right);
        }

        public void Mirror1(TreeNode root) {
            if (root == null) {
                return;
            }
            Mirror(root.left);
            Mirror(root.right);
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
        }
    }

非递归方式:下面这个代码有点意思。

Python 代码:

  class Solution:

        def Mirror(self, root):
            if root is None:
                return
            stack = []
            while root or stack:
                while root:
                    root.left, root.right = root.right, root.left
                    stack.append(root)
                    root = root.left
                if stack:
                    root = stack.pop()
                    root = root.right

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 27 题] “二叉树的镜像”做题记录

链接:https://www.javajike.com/article/3275.html

« [剑指 Offer 第 2 版第 25 题] “合并两个排序的链表”做题记录
[剑指 Offer 第 2 版第 28 题] “对称的二叉树”做题记录»

相关推荐

QR code