当前位置: 首页 > >

二叉树的四种遍历方式【Java实现】

发布时间:

1.前序遍历

前序递归遍历:


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class preorderTraversal {

//前序递归
public List preorderTraversal1(TreeNode root) {
List list = new ArrayList<>();
if (root == null) {
return list;
}
preorder(root, list);
return list;
}

private void preorder(TreeNode node, List list) {
if (node == null) {
return;
}
//根
list.add(node.val);
//左子树
if (node.left != null) {
preorder(node.left, list);
}
//右子树
if (node.right != null) {
preorder(node.right, list);
}
}
}

前序非递归:


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class preorderTraversal {

//前序非递归
public List preorderTraversal(TreeNode root) {
List list = new ArrayList<>();
Stack stack = new Stack<>();
if (root == null) {
return list;
}
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
//将对应节点的val值存起来,一直向左
while (cur != null) {
list.add(cur.val);
stack.add(cur);
cur = cur.left;
}
//改变方向,向右
if (!stack.isEmpty()) {
cur = stack.pop();
cur = cur.right;
}
}
return list;
}
}

2.中序遍历

中序递归:


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class inorderTraversal {
//中序递归
public List inorderTraversal1(TreeNode root) {
List list = new ArrayList<>();
if (root == null) {
return list;
}
inorder(root, list);
return list;
}

private void inorder(TreeNode root, List list) {
if (root == null) {
return;
}
//左子树
inorder(root.left, list);
//根
list.add(root.val);
//右子树
inorder(root.right, list);
}
}

中序非递归:


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class inorderTraversal {

//中序非递归
public List inorderTraversal(TreeNode root) {
List list=new ArrayList<>();
Stack stack=new Stack<>();
TreeNode cur=root;
while(cur!=null||!stack.isEmpty()){
//一直向左
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
//改变方向之前,先将节点的val值存起来
if(!stack.isEmpty()){
cur=stack.pop();
list.add(cur.val);
cur=cur.right;
}
}
return list;
}
}

3.后序遍历

后序递归:


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class postorderTraversal {

//后序递归
public List postorderTraversal1(TreeNode root) {
List list = new ArrayList<>();
if (root == null) {
return list;
}
postorder(root, list);
return list;
}

private void postorder(TreeNode node, List list) {
if (node == null) {
return;
}
//左子树
if (node.left != null) {
postorder(node.left, list);
}
//右子树
if (node.right != null) {
postorder(node.right, list);
}
//根
list.add(node.val);
}
}

后序非递归:


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class postorderTraversal {

//后序非递归
public List postorderTraversal(TreeNode root) {
List list = new ArrayList<>();
Stack stack = new Stack<>();
if (root == null) {
return list;
}
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
//将对应节点的val值存起来,一直向右
while (cur != null) {
list.add(cur.val);
stack.add(cur);
cur = cur.right;
}
//改变方向,向左
if (!stack.isEmpty()) {
cur = stack.pop();
cur = cur.left;
}
}
Collections.reverse(list);
return list;
}
}

4.层序遍历

层序递归:


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class levelOrder {

//层序递归
private List> list = new ArrayList<>();

public List> levelOrder1(TreeNode root) {

if (root == null) {
return list;
}
level(root, 0);
return list;
}

private void level(TreeNode node, int level) {
if (list.size() == level) {
list.add(new ArrayList<>());
}
list.get(level).add(node.val);
if (node.left != null) {
level(node.left, level + 1);
}
if (node.right != null) {
level(node.right, level + 1);
}
}
}

层序非递归:


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class levelOrder {

//层序非递归
public List> levelOrder(TreeNode root) {
List> list = new ArrayList<>();
Queue queue = new LinkedList<>();
if (root == null) {
return list;
}
queue.add(root);
int level = 0;
while (!queue.isEmpty()) {
list.add(new ArrayList<>());
int size = queue.size();
//将这一层的所有节点存起来的同时,将每个节点的左右孩子节点放入队列中
while (size-- != 0) {
TreeNode cur = queue.remove();
list.get(level).add(cur.val);
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null) {
queue.add(cur.right);
}
}
level++;
}
return list;
}
}

?



友情链接: