树的前序遍历、中序遍历、后序遍历,java实现
发布时间:2020-12-15 05:32:16 所属栏目:Java 来源:网络整理
导读:1、三种遍历属于 深度优先搜索( DFS ) , 所谓前中后其实是指遍历时每个节点被访问的相对顺序。 前序遍历。节点→左孩子→右孩子? preorder 中序遍历。左孩子→节点→右孩子? ?inorder 后序遍历。左孩子→右孩子→节点? postorder 2、 宽度优先搜索(BFS)
1、三种遍历属于深度优先搜索( 前序遍历。节点→左孩子→右孩子? preorder 中序遍历。左孩子→节点→右孩子? ?inorder 后序遍历。左孩子→右孩子→节点? postorder 2、宽度优先搜索(BFS)就是从上到下,从左到右一层一层一个一个的访问 上图from leetcode 这样记忆就会很方便。 ? 下面是代码: 一、前序遍历,LinkedList既可以当成栈来使用,又可以当成队列来使用 从根节点开始,每次迭代弹出当前栈顶元素,并将其孩子节点压入栈中,先压右孩子再压左孩子。输出【1,2,3,4,5】 package helloworld; import java.util.LinkedList; class TreeNode{ int val; TreeNode left; TreeNode right; TreeNode(int x){ val=x; } } public class Helloworld{ public LinkedList<Integer> preOrder(TreeNode root){ LinkedList<TreeNode> stack = new LinkedList<>(); LinkedList<Integer> output = new LinkedList<>(); if (root == null) { return output; } stack.add(root); while (!stack.isEmpty()) { TreeNode node = stack.pollLast(); output.add(node.val); if (node.right != null) { stack.add(node.right); } if (node.left != null) { stack.add(node.left); } } return output; } public static void main(String[] args) { Helloworld h=new Helloworld(); TreeNode root = new TreeNode(1); root.left=new TreeNode(2); root.right=new TreeNode(5); root.left.left=new TreeNode(3); root.left.right=new TreeNode(4); System.out.println(h.preOrder(root)); } } 二、中序遍历,输出[3,2,4,1,5] 方法1: 递归 package helloworld; import java.util.ArrayList; import java.util.List; class TreeNode{ int val; TreeNode left; TreeNode right; TreeNode(int x){ val=x; } } public class Helloworld{ public List <Integer> inOrder(TreeNode root){ List < Integer > res = new ArrayList < > (); helper(root,res); return res; } public void helper(TreeNode root,List < Integer > res) { if (root != null) { if (root.left != null) { helper(root.left,res); } res.add(root.val); if (root.right != null) { helper(root.right,res); } } } public static void main(String[] args) { Helloworld h=new Helloworld(); TreeNode root = new TreeNode(1); root.left=new TreeNode(2); root.right=new TreeNode(5); root.left.left=new TreeNode(3); root.left.right=new TreeNode(4); System.out.println(h.inOrder(root)); } } ?方法2,基于栈遍历 package helloworld; import java.util.*; class TreeNode{ int val; TreeNode left; TreeNode right; TreeNode(int x){ val=x; } } public class Helloworld{ public List <Integer> inOrder(TreeNode root){ List < Integer > res = new ArrayList < > (); Stack < TreeNode > stack = new Stack < > (); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { while (curr != null) { stack.push(curr); curr = curr.left; } curr = stack.pop(); res.add(curr.val); curr = curr.right; } return res; } public static void main(String[] args) { Helloworld h=new Helloworld(); TreeNode root = new TreeNode(1); root.left=new TreeNode(2); root.right=new TreeNode(5); root.left.left=new TreeNode(3); root.left.right=new TreeNode(4); System.out.println(h.inOrder(root)); } } 三、后序遍历,输出[3,5,1] package helloworld; import java.util.*; class TreeNode{ int val; TreeNode left; TreeNode right; TreeNode(int x){ val=x; } } public class Helloworld{ public List <Integer> inOrder(TreeNode root){ LinkedList<TreeNode> stack = new LinkedList<>(); LinkedList<Integer> output = new LinkedList<>(); if (root == null) { return output; } stack.add(root); while (!stack.isEmpty()) { TreeNode node = stack.pollLast(); output.addFirst(node.val); if (node.left != null) { stack.add(node.left); } if (node.right != null) { stack.add(node.right); } } return output; } public static void main(String[] args) { Helloworld h=new Helloworld(); TreeNode root = new TreeNode(1); root.left=new TreeNode(2); root.right=new TreeNode(5); root.left.left=new TreeNode(3); root.left.right=new TreeNode(4); System.out.println(h.inOrder(root)); } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
相关内容
- 【代码块】
- java – Android上的NoClassDefFoundError
- java – 在adj矩阵图中查找最大的连通分量?
- java – 当我们使用servlet3规范中提到的AsyncContext时,ht
- 在Eclipse for Java中,是否有类似Visual Studio自定义调试器
- java9学习系列之在docker中如何运行java9
- CCPC-Wannafly & Comet OJ 夏季欢乐赛(2019)H
- java – 如何从该方法中获取方法名称?
- java – 什么时候是StringBuffer / StringBuilder编译器没有
- 所有JVM /系统中的Java,Object.hashCode()结果常量?