java二叉树的遍历方式详解
目录
- 一、前序遍历(递归和非递归)
- 二、中序遍历(递归和非递归)
- 三、后序遍历(递归和非递归)
- 四、层序遍历
- 总结
一、前序遍历(递归和非递归)
前序遍历就是先遍历根再遍历左之后是右 根左右
递归实现:
public List<Integer> preorderTraversal(TreeNode root) { List <Integer> 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); }
迭代实现:
利用栈来实现 先将树的右子树放入栈中,再放入左子树
public List<Integer> preorderTraversal(TreeNode root) { List<Integer> list=new LinkedList<>(); if(root==null) return list; Stack<TreeNode> 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 List<Integer> inorderTraversal(TreeNode root) { List <Integer> 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 List<Integer> inorderTraversal(TreeNode root) { //迭代实现 List<Integer> list =new LinkedList<>(); Stack <TreeNode> 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 List<Integer> postorderTraversal(TreeNode root) { List<Integer> 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 List<Integer> postorderTraversal(TreeNode root) { //利用双栈实现后序遍历 Stack <TreeNode> s1=new Stack<>(); Stack <TreeNode> s2=new Stack<>(); List<Integer> 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<List<Integer>> levelOrder(TreeNode root) { //用队列实现层序遍历 //第一层节点先进队列,出的节点带下一层的节点 List <List<Integer>> list=new ArrayList<>(); if(root==null) return list; Queue<TreeNode> queue=new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ List<Integer> 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; }
总结
本篇文章就到这里了,希望能给你带来帮助,也希望你能够多多关注我们的更多内容!
赞 (0)