美文网首页程序员
剑指offer----二叉树的镜像

剑指offer----二叉树的镜像

作者: qming_c | 来源:发表于2018-02-01 00:22 被阅读0次

第一遍刷剑指offer,每一题都会把具体的思路,以及在网上寻找的优化的点,还有自己二刷三刷之后的想法分享出来。

首先是最简单的一个热身的题-----二叉树镜像

操作给定的二叉树,将其变换为源二叉树的镜像。
输入描述:

二叉树的镜像定义:源二叉树

    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 class Solution {
    public void Mirror(TreeNode root) {
        if(root == null){
            return;
        }
        TreeNode tempNode = root.right;
        root.right = root.left;
        root.left = tempNode;
        Mirror(root.right);
        Mirror(root.left);
    }
}

这种方式很简单,仅仅需要一个TreeNode变量做中间替换,额外空间需求较低,但是在函数调用的过程中,由于是递归的方式,需要一个比较大的函数调用栈,所以也是耗用一定的空间。

遍历方式
public class Solution {
    public void Mirror(TreeNode root) {
        if(root == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode temp = null;
        while(!stack.empty()){
            root = stack.pop();
            temp = root.left;
            root.left = root.right;
            root.right = temp;
            if(root.left != null){
                stack.push(root.left);
            }
            if(root.right != null){
                stack.push(root.right);
            }
        }    
    }

因为要交换每一个节点的两个子节点的位置,遍历的时候为了保证每个树的节点都被遍历到,应该使用常规的深度优先遍历或者广度优先遍历(在这提一下,使用深度优先遍历一般是用来实现的,广度优先遍历使用队列来实现的。在这里我们使用深度优先)

这里我们选择使用栈,先来复习一下jdk中提供的stack数据结构的api。

很简单


StackAPI.png

它只有5个方法
使用遍历的方式解答这个问题,要注意的几个关键的点

  • 循环的结束条件为栈为空。
  • 在OJ中,是没有自动导入包功能的,所以当需要引入一些集合框架中的数据结构的时候OJ需要手动的将类import进来。
  • java中Stack对象的push支持null元素,当你push进一个null之后,size会+1,所以在向栈中添加节点的时候要注意判空。

相关文章

网友评论

    本文标题:剑指offer----二叉树的镜像

    本文链接:https://www.haomeiwen.com/subject/sgrrzxtx.html