全球热资讯！浅谈二叉树遍历

这里就对二叉树的遍历方式进行总结

(相关资料图)

基于递归的遍历前序遍历

前序遍历：即对二叉树按照当前节点、左子树、右子树的顺序进行遍历。显然借助递归，非常容易实现、理解

/***基于递归的前序遍历*/classSolution{publicListpreorderTraversal(TreeNoderoot){Listlist=newLinkedList<>();dfs(root,list);returnlist;}privatevoiddfs(TreeNodecur,Listlist){if(cur==null){return;}//1.处理当前节点list.add(cur.val);//2.处理左子树dfs(cur.left,list);//3.处理右子树dfs(cur.right,list);}}

中序遍历

中序遍历：即对二叉树按照左子树、当前节点、右子树的顺序进行遍历。显然借助递归，非常容易实现、理解

/***基于递归的中序遍历*/classSolution{publicListinorderTraversal(TreeNoderoot){Listlist=newLinkedList<>();dfs(root,list);returnlist;}privatevoiddfs(TreeNodecur,Listlist){if(cur==null){return;}//1.处理左子树dfs(cur.left,list);//2.处理当前节点list.add(cur.val);//3.处理右子树dfs(cur.right,list);}}

后序遍历

后序遍历：即对二叉树按照左子树、右子树、当前节点的顺序进行遍历。显然借助递归，非常容易实现、理解

/***基于递归的后序遍历*/classSolution{publicListpostorderTraversal(TreeNoderoot){Listlist=newLinkedList<>();dfs(root,list);returnlist;}privatevoiddfs(TreeNodecur,Listlist){if(cur==null){return;}//1.处理左子树dfs(cur.left,list);//2.处理右子树dfs(cur.right,list);//3.处理当前节点list.add(cur.val);}}

基于迭代的遍历前序遍历

不同于递归隐式维护栈的便捷，在通过迭代进行遍历时需要我们显式地维护一个栈。具体地，在前序遍历当中。首先需要处理对当前节点进行处理、然后沿着左子树一直入栈。当左子树遍历完毕, 通过出栈获取父节点来对右子树再进行处理

/***基于迭代的前序遍历*/classSolution{publicListpreorderTraversal(TreeNoderoot){Listres=newLinkedList<>();LinkedListstack=newLinkedList<>();while(root!=null||!stack.isEmpty()){while(root!=null){//先处理当前节点res.add(root.val);//然后沿左子树一直入栈stack.addLast(root);root=root.left;}//左子树遍历完毕,通过父节点来对右子树再进行处理TreeNodeparent=stack.removeLast();root=parent.right;}returnres;}}

中序遍历

不同于递归隐式维护栈的便捷，在通过迭代进行遍历时需要我们显式地维护一个栈。具体地，在中序遍历当中。首先沿着左子树一直入栈。当左子树遍历完毕, 通过出栈获取父节点并对其进行处理，最后对右子树再进行处理

/***基于迭代的中序遍历*/classSolution{publicListinorderTraversal(TreeNoderoot){Listres=newLinkedList<>();LinkedListstack=newLinkedList<>();while(root!=null||!stack.isEmpty()){while(root!=null){//先沿左子树一直入栈stack.addLast(root);root=root.left;}//左子树遍历完毕,获取父节点TreeNodeparent=stack.removeLast();//处理父节点的值res.add(parent.val);//通过父节点对右子树再进行处理root=parent.right;}returnres;}}

后序遍历

后序遍历的顺序是左、右、当前。如果直接使用栈按这个顺序进行遍历输出会比较麻烦。故我们可以先按照当前、右、左的顺序进行迭代遍历，显然这个过程与前序遍历非常类似，只是需要把代码中涉及左、右子树的调换下即可。最后对遍历结果进行翻转。这样遍历结果就由当前、右、左 就变为 左、右、当前。即我们所需的后序遍历结果

/***基于迭代的后序遍历*/classSolution{publicListpostorderTraversal(TreeNoderoot){Listres=newLinkedList<>();LinkedListstack=newLinkedList<>();//先按根、右、左的顺序进行遍历while(root!=null||!stack.isEmpty()){while(root!=null){//先处理当前节点res.add(root.val);//然后沿右子树一直入栈stack.addLast(root);root=root.right;}//右子树遍历完毕,通过父节点获取左子树再进行处理TreeNodeparent=stack.removeLast();root=parent.left;}//对遍历结果进行翻转//这样遍历结果就由根、右、左就变为左、右、根,即后序遍历Collections.reverse(res);returnres;}}

层序遍历

对于二叉树的层序遍历就简单很多了。我们借助队列的FIFO特性即可轻松实现

classSolution{publicListlevelOrder(TreeNoderoot){Listres=newLinkedList<>();if(root==null){returnres;}Queuequeue=newLinkedList<>();queue.add(root);while(!queue.isEmpty()){//弹出队首元素,进行处理TreeNodecur=queue.poll();res.add(node.val);//将当前节点的左、右子节点加入队列if(node.left!=null){queue.add(node.left);}if(node.right!=null){queue.add(node.right);}}returnres;}}

基于Morris算法的遍历基本原理

Morris算法为二叉树的遍历提供了新的思路，其通过充分利用树中叶子节点存在大量空指针这一特点。实现了常数级别的空间复杂度。在进一步介绍该算法之前，我们先来说明一个概念——mostRight节点。其用于表示当前节点cur的左子树的最右节点。例如下图的一个二叉树。如果当前节点为1，则mostRight节点即为5；如果当前节点为3，则mostRight节点即为6

实际上，Morris算法非常简单。其基本遍历流程如下：

将当前节点cur初始化为root当前节点cur如果不存在左子树。则将当前节点指向其右子树，以便遍历当前节点的右子树当前节点cur如果存在左子树，则先获取cur节点的mostRight节点如果mostRight节点的右子节点为空，此时说明cur节点的左子树还未遍历。故：一方面，我们将mostRight节点的右子节点设置为cur节点；另一方面，将当前节点指向其左子树，以便遍历当前节点的左子树如果mostRight节点的右子节点为当前节点cur，此时说明cur节点的左子树已经遍历完成。故：一方面，我们将mostRight节点的右子节点设置为null空指针；另一方面，将当前节点指向其右子树，以便遍历当前节点的右子树重复Step 2、Step 3，直到当前节点cur为null时为止

该算法遍历过程的示意图如下，可以看到当一个节点的左子树未遍历完时，Morris算法会利用原叶子节点的null空指针修改树。而当该节点的左子树遍历后，会把对树的修改进行撤回。以恢复树原有的结构

前序遍历

这里基于Morris算法来实现前序遍历。问题的关键就在于何时对当前节点进行处理。显然这里有两个时机，一方面，遍历过程中发现当前节点的左子树为空。则在对当前节点的右子树进行遍历前，需要对当前节点进行处理；另一方面，遍历过程中发现当前节点的左子树不为空，则在对当前节点的左子树进行遍历前，需要对当前节点进行处理

/***基于Morris算法的前序遍历*/classSolution{publicListpreorderTraversal(TreeNoderoot){Listres=newLinkedList<>();if(root==null){returnres;}TreeNodecur=root;//当前节点cur的左子树的最右节点TreeNodemostRight=null;while(cur!=null){//当前节点的左子树为空if(cur.left==null){//处理当前节点res.add(cur.val);//处理当前节点的右子树cur=cur.right;}else{//当前节点的左子树不为空//寻找当前节点cur的左子树的最右节点mostRight=cur.left;while(mostRight.right!=null&&mostRight.right!=cur){mostRight=mostRight.right;}if(mostRight.right==null){//说明cur节点的左子树未遍历//处理当前节点res.add(cur.val);//处理当前节点的左子树mostRight.right=cur;cur=cur.left;}elseif(mostRight.right==cur){//说明cur节点的左子树已经遍历完成//处理当前节点的右子树mostRight.right=null;cur=cur.right;}}}returnres;}}

中序遍历

这里基于Morris算法来实现中序遍历。问题的关键就在于何时对当前节点进行处理。显然这里有两个时机，一方面，遍历过程中发现当前节点的左子树为空。则在对当前节点的右子树进行遍历前，需要对当前节点进行处理；另一方面，遍历过程中发现当前节点的左子树不为空，则在对当前节点的左子树完成遍历后，需要对当前节点进行处理

/***基于Morris算法的中序遍历*/classSolution{publicListinorderTraversal(TreeNoderoot){Listres=newLinkedList<>();if(root==null){returnres;}TreeNodecur=root;//当前节点cur的左子树的最右节点TreeNodemostRight=null;while(cur!=null){//当前节点的左子树为空if(cur.left==null){//处理当前节点res.add(cur.val);//处理当前节点的右子树cur=cur.right;}else{//当前节点的左子树不为空//寻找当前节点cur的左子树的最右节点mostRight=cur.left;while(mostRight.right!=null&&mostRight.right!=cur){mostRight=mostRight.right;}if(mostRight.right==null){//说明cur节点的左子树未遍历//处理当前节点的左子树mostRight.right=cur;cur=cur.left;}elseif(mostRight.right==cur){//说明cur节点的左子树已经遍历完成//处理当前节点res.add(cur.val);//处理当前节点的右子树mostRight.right=null;cur=cur.right;}}}returnres;}}

Note

这里给出本文中关于树节点的类定义

/***树的节点*/classTreeNode{TreeNodeleft;TreeNoderight;intval;TreeNode(){}TreeNode(intval){this.val=val;}TreeNode(intval,TreeNodeleft,TreeNoderight){this.val=val;this.left=left;this.right=right;}}

关键词： 进行处理