二叉树递归迭代及morris层序前中后序遍历详解

目录
  • 分析二叉树的前序,中序,后序的遍历步骤
    • 1.层序遍历
      • 方法一:广度优先搜索
      • 方法二:递归
  • 2.前序遍历
  • 3.中序遍历
  • 4.后序遍历
  • 递归解法
    • 前序遍历--递归
  • 迭代解法
    • 前序遍历--迭代
      • 核心思想:
    • 三种迭代解法的总结:
    • Morris遍历
    • morris--前序遍历
    • morris--中序遍历
    • morris--后序遍历:

分析二叉树的前序,中序,后序的遍历步骤

1.层序遍历

方法一:广度优先搜索

  (以下解释来自leetcode官方题解)

我们可以用广度优先搜索解决这个问题。

我们可以想到最朴素的方法是用一个二元组 (node, level) 来表示状态,它表示某个节点和它所在的层数,每个新进队列的节点的 level 值都是父亲节点的 level 值加一。最后根据每个点的 level 对点进行分类,分类的时候我们可以利用哈希表,维护一个以 level 为键,对应节点值组成的数组为值,广度优先搜索结束以后按键 level 从小到大取出所有值,组成答案返回即可。

考虑如何优化空间开销:如何不用哈希映射,并且只用一个变量 node 表示状态,实现这个功能呢?

我们可以用一种巧妙的方法修改广度优先搜索:

  •  首先根元素入队
  •  当队列不为空的时候,

求当前队列的长度 S_i; 

依次从队列中取 S_i 个元素进行拓展,然后进入下一次迭代.

它和普通广度优先搜索的区别在于,普通广度优先搜索每次只取一个元素拓展,而这里每次取 S_i个元素。在上述过程中的第 i 次迭代就得到了二叉树的第 i 层的 S_i 个元素。

为什么这么做是对的呢?我们观察这个算法,可以归纳出这样的循环不变式:第 i 次迭代前,队列中的所有元素就是第 i 层的所有元素,并且按照从左向右的顺序排列。证明它的三条性质(你也可以把它理解成数学归纳法):

初始化:i=1 的时候,队列里面只有 root,是唯一的层数为 1 的元素,因为只有一个元素,所以也显然满足「从左向右排列」;
保持:如果 i=k 时性质成立,即第 k 轮中出队 S_k的元素是第 k 层的所有元素,并且顺序从左到右。因为对树进行广度优先搜索的时候由低 k 层的点拓展出的点一定也只能是 k+1 层的点,并且 k+1 层的点只能由第 k 层的点拓展到,所以由这 S_k 个点能拓展到下一层所有的 S_k+1  个点。又因为队列的先进先出(FIFO)特性,既然第 k 层的点的出队顺序是从左向右,那么第 k+1 层也一定是从左向右。至此,我们已经可以通过数学归纳法证明循环不变式的正确性。
终止:因为该循环不变式是正确的,所以按照这个方法迭代之后每次迭代得到的也就是当前层的层次遍历结果。至此,我们证明了算法是正确的。

广度优先搜索的简化步骤为

初始化队列 q,并将根节点 root 加入到队列中;
当队列不为空时:
队列中弹出节点 node,加入到结果中;
如果左子树非空,左子树加入队列;
如果右子树非空,右子树加入队列;
由于题目要求每一层保存在一个子数组中,所以我们额外加入了 level 保存每层的遍历结果,并使用 for 循环来实现。

看个图例用以说明:

广度优先需要用队列作为辅助结构,我们先将根节点放到队列中,然后不断遍历队列。

首先拿出根节点,如果左子树/右子树不为空,就将他们放入队列中。第一遍处理完后,根节点已经从队列中拿走了,而根节点的两个孩子已放入队列中了,现在队列中就有两个节点 2 和 5。

第二次处理,会将 2 和 5 这两个节点从队列中拿走,然后再将 2 和 5 的子节点放入队列中,现在队列中就有三个节点 3,4,6。

我们把每层遍历到的节点都放入到一个结果集中,最后返回这个结果集就可以了。

public List<List<Integer>> levelOrder(TreeNode root) {
        //返回的结果
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(null == root){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        //根节点入队
        queue.add(root);
        while(!queue.isEmpty()){
            //一层的结果
            List<Integer> level = new ArrayList<Integer>();
            int levelCount = queue.size();
            //添加节点到一层的List中去
            for(int i = 0; i < levelCount ; i ++){
                //节点出队
                TreeNode node = queue.remove();
                //节点的左子树入队
                if(node.left != null){
                  queue.add(node.left);
                }
                //节点的右子树入队
                if(node.right != null){
                  queue.add(node.right);
                }
                level.add(node.val);
            }
            res.add(level);
        }
        return res;
    }

方法二:递归

用广度优先处理是很直观的,可以想象成是一把刀横着切割了每一层,但是深度优先遍历就不那么直观了。

我们开下脑洞,把这个二叉树的样子调整一下,摆成一个田字形的样子。田字形的每一层就对应一个 list。

按照深度优先的处理顺序,会先访问节点 1,再访问节点 2,接着是节点 3。
之后是第二列的 4 和 5,最后是第三列的 6。

每次递归的时候都需要带一个 index(表示当前的层数),也就对应那个田字格子中的第几行,如果当前行对应的 list 不存在,就加入一个空 list 进去。

public List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(root==null) {
			return res;
		}
		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
		//将根节点放入队列中,然后不断遍历队列
		queue.add(root);
		while(queue.size()>0) {
			//获取当前队列的长度,这个长度相当于 当前这一层的节点个数
			int size = queue.size();
			ArrayList<Integer> tmp = new ArrayList<Integer>();
			//将队列中的元素都拿出来(也就是获取这一层的节点),放到临时list中
			//如果节点的左/右子树不为空,也放入队列中
			for(int i=0;i<size;++i) {
				TreeNode t = queue.remove();
				tmp.add(t.val);
				if(t.left!=null) {
					queue.add(t.left);
				}
				if(t.right!=null) {
					queue.add(t.right);
				}
			}
			//将临时list加入最终返回结果中
			res.add(tmp);
		}
		return res;
}

2.前序遍历

2.1先输出当前节点(初始的时候是root节点)

2.2如果左子节点不为空,则递归继续前序遍历

2.3如果右子节点不为空,则递归继续前序遍历

3.中序遍历

3.1如果当前节点的左子节点不为空,则递归中序遍历

3.2输出当前节点

3.3如果当前节点的右子节点不为空,则递归中序遍历

4.后序遍历

4.1如果当前节点的左子节点不为空,则递归后序遍历

4.2如果当前节点的右子节点不为空,则递归后序遍历

4.3输出当前节点

如果你按照 根节点 -> 左孩子 -> 右孩子 的方式遍历,即「先序遍历」,每次先遍历根节点,遍历结果为 1 2 4 5 3 6 7;

同理,如果你按照 左孩子 -> 根节点 -> 右孩子 的方式遍历,即「中序序遍历」,遍历结果为 4 2 5 1 6 3 7;

如果你按照 左孩子 -> 右孩子 -> 根节点 的方式遍历,即「后序序遍历」,遍历结果为 4 5 2 6 7 3 1;

最后,层序遍历就是按照每一层从左向右的方式进行遍历,遍历结果为 1 2 3 4 5 6 7。

递归解法

由于层次遍历的递归解法不是主流,因此只介绍前三种的递归解法

前序遍历--递归

public List<Integer> preorderTraversal(TreeNode root) {
        //递归
        List<Integer> list = new ArrayList<>();
        preOrder(root,list);
        return list;
    }
    public void preOrder(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        list.add(root.val);
        preOrder(root.left,list);
        preOrder(root.right,list);
}

中序遍历--递归

public List<Integer> inorderTraversal(TreeNode root) {
        //递归
        List<Integer> list = new LinkedList<>();
        inOrder(root,list);
        return list;
    }
    public void inOrder(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        inOrder(root.left,list);
        list.add(root.val);
        inOrder(root.right,list);
}

后序遍历--递归

public List<Integer> postorderTraversal(TreeNode root) {
        //递归
        List<Integer> list = new LinkedList<>();
        postOrder(root,list);
        return list;
    }
    public void postOrder(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        postOrder(root.left,list);
        postOrder(root.right,list);
        list.add(root.val);
}

三种递归遍历的总结:递归终止的条件为碰到空节点。

迭代解法

前序遍历--迭代

核心思想:

1.每拿到一个节点就把它保存在栈中

2.继续对这个节点的左子树重复过程1,直到左子树为空

3.因为保存在栈中的节点都遍历了左子树但是没有遍历右子树,所以对栈中节点出栈并对它的右子树重复过程1

4.直到遍历完所有节点

public List<Integer> preorderTraversal(TreeNode root) {
        //迭代
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        //临时节点,帮助遍历二叉树
        TreeNode node = root;
        //栈的作用是用来短暂的保存遍历节点的值,以助于最后值的返回
        while(!stack.isEmpty() || node != null){
            while(node != null){
                list.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return list;
}

中序遍历--迭代

public List<Integer> inorderTraversal(TreeNode root) {
        //迭代
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        while(!stack.isEmpty() || root != null){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);//出栈的时候才将父节点 的值加入到结果中
            root = root.right;
        }
        return list;
}

和前序遍历的代码完全相同,只是在出栈的时候才将父节点 的值加入到结果中。

后序遍历--迭代

public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> list = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                list.addFirst(root.val);//addFirst():向链表首部添加元素
                root = root.right;
            } else {
                root = stack.pop();
                root = root.left;
            }
        }
        return list;
}

三种迭代解法的总结:

前序遍历和后序遍历之间的关系:

前序遍历顺序为:根 -> 左 -> 右

后序遍历顺序为:左 -> 右 -> 根

如果1: 将前序遍历中节点插入结果链表尾部的逻辑,修改为将节点插入结果链表的头部

那么结果链表就变为了:右 -> 左 -> 根

如果2: 将遍历的顺序由从左到右修改为从右到左,配合如果1

那么结果链表就变为了:左 -> 右 -> 根

这刚好是后序遍历的顺序

基于这两个思路,想一下如何处理:

修改前序遍历代码中,节点写入结果链表的代码,将插入队尾修改为插入队首

修改前序遍历代码中,每次先查看左节点再查看右节点的逻辑,变为先查看右节点再查看左节点

前序遍历和中序遍历之间的关系:

和前序遍历的代码完全相同,只是在出栈的时候才将父节点的值加入到结果中。

Morris遍历

遍历特点:Morris 遍历利用了树中大量空闲指针的特性

当前节点cur,一开始cur来到整树头

1)cur无左树,cur  = cur.right(cur右移)

2)cur有左树,找到左树最右节点,mostright;此时我们又可以分为两种情况,一种是叶子节点添加 right 指针的情况,一种是去除叶子节点 right 指针的情况

 A.mostright 的右指针指向null的mostright.right = cur,  cur = cur.left(cur左移)

 B.mostright 的右指针指向cur的mostright.right = null(为了防止重复执行,则需要去掉 right 指针),      cur = cur.right(cur右移)

当cur == null时,整个过程结束。

遍历特点:有左树节点必遍历到两次,没有左树的节点必遍历到一次

public static void morris(Node head){
    if(head == null){
        return;
    }
    Node cur = head;
    Node mostRight = null;
    while(cur != null){
        //cur有没有左树
        mostRight = cur.left;
        if(mostRight != null){//有左树的情况
            //找到cur左树上,真实的最右节点
            //前者说明是第一次来到当前的cur,后者说明是第二次来到当前的cur
            while(mostRight.right != null && mostRight.right != cur){
                mostRight = mostRight.right;
            }
            //从while中出来,mostRight一定是cur左树上的最右节点
            if(mostRight.right == null){
                mostRight.right = cur;
                cur = cur.left;
                continue;//结束的是外层的循环!!!!!!!!!!!!!
            }else{//走到这里意味着:mostRight.right == cur
                mostRight.right = null;
            }
        }
        //cur没有左树
        cur = cur.right;
    }
}

空间复杂度:利用空闲的指针,使用了两个变量完成了遍历,空间复杂度是常数级别的

时间复杂度: 

morris--前序遍历

第一次来到一个节点,就打印;第二次来到这个节点,不打印

public static void morrisPre(Node head){
    if(head == null){
        return;
    }
    Node cur = head;
    Node mostRight = null;
    while(cur != null){
        mostRight = cur.left;
        if(mostRight != null){
            while(mostRight.right != null && mostRight.right != cur){
                mostRight = mostRight.right;
            }
            if(mostRight.right == null){
                mostRight.right = cur;
                System.out.print(cur.value + " ");
                cur = cur.left;
                continue;
            }else{
                mostRight.right = null;
            }
        }else{
            System.out.print(cur.value + " ");
        }
        cur = cur.right;
    }
    System.out.println();
}

morris--中序遍历

对于能回到自己两次的节点,第二次时打印,对于只能来到自己一次的节点,直接打印

只要一个节点要往右移动,就打印

public static void morrisIn(Node head){
    if(head == null){
        return;
    }
    Node cur = head;
    Node mostRight = null;
    while(cur != null){
        mostRight = cur.left;
        if(mostRight != null){
            while(mostRight.right != null && mostRight.right != cur){
                mostRight = mostRight.right;
            }
            if(mostRight.right == null){
                mostRight.right = cur;
                cur = cur.left;
                continue;
            }else{
                mostRight.right = null;
            }
        }
        System.out.print(cur.value + " ");
        cur = cur.right;
    }
    System.out.println();
}

morris--后序遍历:

public static void morrisPos(Node head) {
		if(head == null) {
			return;
		}
		Node cur = head;
		Node mostRight = null;
		while(cur != null) {
			mostRight = cur.left;
			if(mostRight != null) {
				while(mostRight.right != null && mostRight.right != cur) {
					mostRight = mostRight.right;
				}
				if(mostRight.right == null) {
					mostRight.right = cur;
					cur = cur.left;
					continue;
				}else {
					mostRight.right = null;
					printEdge(cur.left);//逆序打印左树的右边界
				}
			}
			cur = cur.right;
		}
		printEdge(head);//最后打印整棵树的右边界
		System.out.println();
	}
 	public static void printEdge(Node head) {
		Node tail = reverseEdge(head);
		Node cur = tail;
		while(cur != null) {
			System.out.print(cur.value + " ");
			cur = cur.right;
		}
		reverseEdge(tail);
	}
	private static Node reverseEdge(Node from) {
		Node pre = null;
		Node next = null;
		while(from != null) {
			next = from.right;
			from.right = pre;
			pre = from;
			from = next;
		}
		return pre;
	}

Morris后序遍历比较复杂,可以看看相关的视频讲解--左神算法系列。

以上就是二叉树递归迭代及morris层序前中后序遍历详解的详细内容,更多关于二叉树递归迭代遍历详解的资料请关注我们其它相关文章!

时间: 2021-11-22

java二叉树的遍历方式详解

目录 一.前序遍历(递归和非递归) 二.中序遍历(递归和非递归) 三.后序遍历(递归和非递归) 四.层序遍历 总结 一.前序遍历(递归和非递归) 前序遍历就是先遍历根再遍历左之后是右 根左右 递归实现: public List<Integer> preorderTraversal(TreeNode root) { List <Integer> list=new ArrayList<>(); pre(root,list); return list; } public vo

Java二叉树的遍历思想及核心代码实现

二叉树在计算机中的存储方式往往线性结构,线性存储分为顺序存储和链式存储,将二叉树按层序编号. 顺序结构:按编号的顺序进行存储,对于完全二叉树而言,顺序存储可以反映二叉树的逻辑,但是对于大多数的二叉树则无法反映其逻辑关系,不过可以用 ^ 来代替不存在的结点,但是如果这个树是一个右斜树,就非常浪费存储空间.所以二叉树的存储形式一般为链式存储结构. 链式存储:每一个结点都分有一个数据域(data)和两个指针域(lchild和rchild),指针域分别指向左孩子和右孩子,若为空则为null.遍历方式有四

Java实现的二叉树常用操作【前序建树,前中后递归非递归遍历及层序遍历】

本文实例讲述了Java实现的二叉树常用操作.分享给大家供大家参考,具体如下: import java.util.ArrayDeque; import java.util.Queue; import java.util.Stack; //二叉树的建树,前中后 递归非递归遍历 层序遍历 //Node节点 class Node { int element; Node left; Node right; public Node() { } public Node(int element) { this.

Python二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】

本文实例讲述了Python二叉树的遍历操作.分享给大家供大家参考,具体如下: # coding:utf-8 """ @ encoding: utf-8 @ author: lixiang @ email: lixiang_cn@foxmail.com @ python_version: 2 @ time: 2018/4/11 0:09 @ more_info: 二叉树是有限个元素的集合,该集合或者为空.或者有一个称为根节点(root)的元素及两个互不相交的.分别被称为左子树和

JS中的二叉树遍历详解

二叉树是由根节点,左子树,右子树组成,左子树和友子树分别是一个二叉树. 这篇文章主要在JS中实现二叉树的遍历. 一个二叉树的例子 var tree = { value: 1, left: { value: 2, left: { value: 4 } }, right: { value: 3, left: { value: 5, left: { value: 7 }, right: { value: 8 } }, right: { value: 6 } } } 广度优先遍历 广度优先遍历是从二叉树

JavaScript知识点总结(十一)之js中的Object类详解

JavaScript中的Object对象,是JS中所有对象的基类,也就是说JS中的所有对象都是由Object对象衍生的.Object对象主要用于将任意数据封装成对象形式. 一.Object类介绍 Object类是所有JavaScript类的基类(父类),提供了一种创建自定义对象的简单方式,不再需要程序员定义构造函数. 二.Object类主要属性 1.constructor:对象的构造函数. 2.prototype:获得类的prototype对象,static性质. 三.Object类主要方法 1

在Node.js中使用Javascript Generators详解

Generators是Javascript的一种协同程序( coroutine 简称:协程)风格,是指那些可以在执行时暂停然后又恢复的函数,该函数是在functi配以星号符号形式如function* ,函数内有些特征关键词如yield 和yield*. function* generatorFn () { console.log('look ma I was suspended') } var generator = generatorFn() // [1] setTimeout(functio

JS中多种方式创建对象详解

1.内置对象创建 var girl=new Object(); girl.name='hxl'; console.log(typeof girl); 2.工厂模式,寄生构造函数模式 function Person(name){ var p=new Object();//内部进行实例化 p.name=name; p.say=function(){ console.log('my name is '+ p.name); } return p;//注:一定要返回 } var girl=Person('

JS中Attr的用法详解

具体代码如下所示: <script type="text/javascript" src="js/jquery-1.8.0.min.js"></script> <script type="text/javascript"> $(document).ready(function(){ $("#btn").click(function(){ //使用attr(name)获取属性值: alert(

Angular.JS中的this指向详解

[this详解] 1.谁最终调用函数,this指向谁. ① this指向的,永远只可能是对象!!!!!! ② this指向谁,永远不取决于this写在哪!!而是取决于函数在哪调用. ③ this指向的对象,我们称之为函数的上下文context,也叫函数的调用者 2.※※※※※this指向的规律(与函数调用的方式息息相关): this指向的情况,取决于函数调用的方式有哪些: ① 通过函数名()直接调用:this指向window ② 通过对象.函数名()调用的:this指向这个对象 ③ 函数作为数组

js中this用法实例详解

本文实例讲述了js中this用法.分享给大家供大家参考.具体如下: 1. 指向window 全局变量 alert(this) //返回 [object Window] 全局函数 function sayHello(){ alert(this); } sayHello(); 2. 指向该对象(在全局里面this指向window,在某个对象里面this指向该对象,在闭包里面this指向window) var user="the Window"; var box={ user:'the bo

node.js中的require使用详解

代码注释里已经描述的非常的清晰,这里就不多废话了,直接奉上代码: 复制代码 代码如下: /*在node中,可以使用require()函数来加载模块.  * require函数使用一个参数,参数值可以带有完整路径的模块的文件名,也可以为模块名.当使用node中提供的模块时,在require函数中只需要指定模块名即可.  * */ //建立一个页面2.js;代码如下 var name="思思博士"; exports.name=name; //建立一个页面1.js;代码如下 var two=

node.js中的事件处理机制详解

EventEmitter类 在Node.js的用于实现各种事件处理的event模块中,定义了一个EventEmitter类.所有可能触发事件的对象都是一个集成了EventEmitter类的子类的实例对象,在Node.js中,为EventEmitter类定义了许多方法,所有与对象的事件处理函数的绑定及解除相关的处理均依靠这些方法的调用来执行. EventEmitter类的各种方法 event:代表事件名 listener:代表事件处理函数 中括号内的参数代表该参数为可选参数 方法名与参数 描述 a

JS中的多态实例详解

多态在面向对象编程语言中是十分重要的.在JAVA中是通过继承来得到多态的效果.如下: public abstract class Animal { abstract void makeSound(); // 抽象方法 } public class Chicken extends Animal{ public void makeSound(){ System.out.println( "咯咯咯" ); } } public class Duck extends Animal{ publi