java二叉树的遍历方式详解

java二叉树的遍历方式详解

目录一、前序遍历（递归和非递归）二、中序遍历（递归和非递归）三、后序遍历（递归和非递归）四、层序遍历总结

一、前序遍历（递归和非递归）

前序遍历就是先遍历根再遍历左之后是右 根左右

递归实现：

public List preorderTraversal(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);

}

迭代实现：

利用栈来实现 先将树的右子树放入栈中，再放入左子树

public List preorderTraversal(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 List inorderTraversal(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 List inorderTraversal(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 List postorderTraversal(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 List postorderTraversal(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-ISRIvyxD-;

}

list.add(list1);

}

return list;

}

总结

本篇文章就到这里了，希望能给你带来帮助，也希望你能够多多关注我们的更多内容！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。