[剑指 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/