java二叉树的遍历方式详解
目录
- 一、前序遍历(递归和非递归)
- 二、中序遍历(递归和非递归)
- 三、后序遍历(递归和非递归)
- 四、层序遍历
- 总结
一、前序遍历(递归和非递归) 前序遍历就是先遍历根再遍历左之后是右 根左右
递归实现:
public ListpreorderTraversal(TreeNode root) {List list=new ArrayList<>(); pre(root,list); return list; }public void pre(TreeNode root,List list){if(root==null){return ; }list.add(root.val); pre(root.left,list); pre(root.right,list); }
【java二叉树的遍历方式详解】迭代实现:
利用栈来实现 先将树的右子树放入栈中,再放入左子树
public ListpreorderTraversal(TreeNode root) {List list=new LinkedList<>(); if(root==null) return list; Stack stack=new Stack<>(); stack.push(root); while(!stack.isEmpty()){TreeNode node=stack.pop(); list.add(node.val); if(node.right!=null) stack.push(node.right); if(node.left!=null) stack.push(node.left); }return list; }
二、中序遍历(递归和非递归) 中序遍历就是先遍历左再遍历根,最后遍历右 左根右
递归实现:
public ListinorderTraversal(TreeNode root) {List list=new ArrayList<>(); inorder(root,list); return list; }public void inorder(TreeNode root,List list){if(root==null){return ; }inorder(root.left,list); list.add(root.val); inorder(root.right,list); }
迭代实现
利用栈来实现,二叉树的中序遍历,由于中序遍历是左根右,先定义节点找到最左节点入栈,之后出栈,判断该节点是否有右孩子
public ListinorderTraversal(TreeNode root) {//迭代实现 List list =new LinkedList<>(); Stack stack=new Stack<>(); TreeNode cur=root; while(cur!=null||!stack.isEmpty()){//先找到左节点while(cur!=null){stack.push(cur); cur=cur.left; }TreeNode node=stack.pop(); list.add(node.val); if(node.right!=null){cur=node.right; }}return list; }
三、后序遍历(递归和非递归) 后序遍历就是左右根
递归实现:
public ListpostorderTraversal(TreeNode root) {List list=new ArrayList<>(); postorder(root,list); return list; }public void postorder(TreeNode root,List list){if(root==null){return ; }postorder(root.left,list); postorder(root.right,list); list.add(root.val); }
非递归实现:
用两个栈来实现二叉树的后序遍历
第一个栈先放入根节点,之后弹出放入第二个节点,之后第一个栈放入左右孩子,之后再弹出放入第二个栈,即可实现
public ListpostorderTraversal(TreeNode root) {//利用双栈实现后序遍历Stack s1=new Stack<>(); Stack s2=new Stack<>(); List list=new LinkedList<>(); if(root==null) return list; s1.push(root); while(!s1.isEmpty()){TreeNode node=s1.pop(); s2.push(node); if(node.left!=null) s1.push(node.left); if(node.right!=null) s1.push(node.right); }while(!s2.isEmpty()){TreeNode cur=s2.pop(); list.add(cur.val); }return list; }
四、层序遍历 用队列实现层序遍历
public List> levelOrder(TreeNode root) {//用队列实现层序遍历//第一层节点先进队列,出的节点带下一层的节点List
> list=new ArrayList<>(); if(root==null) return list; Queue
queue=new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){List list1=new ArrayList<>(); int size=queue.size(); while(size!=0){TreeNode cur=queue.poll(); list1.add(cur.val); if(cur.left!=null){queue.offer(cur.left); }if(cur.right!=null){queue.offer(cur.right); }size--; }list.add(list1); }return list; }
总结 本篇文章就到这里了,希望能给你带来帮助,也希望你能够多多关注脚本之家的更多内容!
推荐阅读
- JAVA(抽象类与接口的区别&重载与重写&内存泄漏)
- 【生信技能树】R语言练习题|【生信技能树】R语言练习题 - 中级
- 事件代理
- Java|Java OpenCV图像处理之SIFT角点检测详解
- java中如何实现重建二叉树
- 数组常用方法一
- 【Hadoop踩雷】Mac下安装Hadoop3以及Java版本问题
- 种树郭橐驼传(文言句式+古今异义+词类活用+通假字)
- Java|Java基础——数组
- RxJava|RxJava 在Android项目中的使用(一)