首页 > 其他 > 详细

剑指 Offer 27. 二叉树的镜像

时间:2020-08-18 20:20:45      阅读:72      评论:0      收藏:0      [点我收藏+]

题目链接

剑指 Offer 27. 二叉树的镜像

题目描述

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

技术分享图片

解题思路

1.递归

之前说过了,二叉树的题目基本上可以利用递归来完成,镜像二叉树实现的本质在于将某个节点的左子树和右子树交换即可。递归代码的具体实现借鉴了后序遍历!

2.非递归

在我脑海已经有点固化了:递归的代码如果要变为迭代的方式,一定要采用栈。然而本题出现了意外,利用队列实现非递归。采用了从上向下的思想。

先把root根节点压入队列中,然后交换root根节点的左右子树,交换完毕后,如果root.left不为空压入队列中,如果root.right不为空,压入队列中,重复以上操作只到队列为空即可。

AC代码

1.递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

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

    public TreeNode invertTree(TreeNode root) {
        dfs(root);
        return root;
    }
}

2.非递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return root;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            TreeNode head = q.poll();
            TreeNode temp = head.left;
            head.left = head.right;
            head.right = temp;
            if(head.left != null) q.offer(head.left);
            if(head.right != null) q.offer(head.right);
        }
        return root;
    }
}

剑指 Offer 27. 二叉树的镜像

原文:https://www.cnblogs.com/XDU-Lakers/p/13525461.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!