剑指Offer（十八）-- 二叉树的镜像

秦怀杂货店

发布于 2022-02-15 13:42:18

2960

发布于 2022-02-15 13:42:18

文章被收录于专栏：技术杂货店

题目描述
思路与解答

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像。

输入描述:

二叉树的镜像

源二叉树      8
     /  \
    6   10
   / \  / \
  5  7 9 11
  镜像二叉树
      8
     /  \
    10   6
   / \  / \
  11 9 7   5

思路与解答

使用递归，直接将左子树反转，右子树反转，交换即可。值得注意的是，反转后的结果需要先保存，左右两个都反转之后，才能赋值。

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/

public static void Mirror(TreeNode root) {
    if (root == null) {
        return;
    } else {
        root = reverse(root);
    }
}

public static TreeNode reverse(TreeNode root) {
    if (root == null) {
        return root;
    } else {
        TreeNode left = reverse(root.right);
        TreeNode right = reverse(root.left);
        root.left = left;
        root.right =right;
        return root;
    }
}

那这道题如果不用递归怎么做？

其实我们可以使用栈来完成，先把根节点压进栈，循环判断栈是否为空，不为空则取出第一个元素，交换左右节点，然后将左右节点只要不为null，压进栈即可，循环直到栈为空。

show you the code!!!

    public static void Mirror(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            TreeNode tempNode = node.left;
            node.left = node.right;
            node.right = tempNode;
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
    }

此文章仅代表自己（本菜鸟）学习积累记录，或者学习笔记，如有侵权，请联系作者删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有错误之处，还望指出，感激不尽~

技术之路不在一时，山高水长，纵使缓慢，驰而不息。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-11-24，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树