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 ;
}
pre(root.left,list);
pre(root.right,list);
}
```

``` public List preorderTraversal(TreeNode root) {
if(root==null) return list;
Stack  stack=new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node=stack.pop();
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);
inorder(root.right,list);
}
```

``` public List inorderTraversal(TreeNode root) {
//迭代实现
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();
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);
}
```

``` public List postorderTraversal(TreeNode root) {
//利用双栈实现后序遍历
Stack  s1=new Stack<>();
Stack  s2=new Stack<>();
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();
}
return list;
}
```

四、层序遍历

```public List> levelOrder(TreeNode root) {
//用队列实现层序遍历
//第一层节点先进队列，出的节点带下一层的节点
List > list=new ArrayList<>();
if(root==null) return list;
queue.offer(root);
while(!queue.isEmpty()){
List list1=new ArrayList<>();
int size=queue.size();
while(size!=0){
TreeNode cur=queue.poll();
if(cur.left!=null){
queue.offer(cur.left);
}
if(cur.right!=null){
queue.offer(cur.right);
}
size--;
}