这个题就是考察你对树的遍历
1.递归解法
我用了三个集合存放每次遍历结果，再进行一次遍历把每次存放到二维结果数组中。时间复杂度：O（n），遍历所有结点；空间复杂度：O（n），递归的深度。
import java.util.*;

/*

  • public class TreeNode {
  • int val = 0;
  • TreeNode left = null;
  • TreeNode right = null;
  • }
  • /

public class Solution {
/*
*
* @param root TreeNode类 the root of binary tree
* @return int整型二维数组
*/
//用于存放每次遍历结果
List<integer> list1=new ArrayList<>();
List<integer> list2=new ArrayList<>();
List<integer> list3=new ArrayList<>();
public int[][] threeOrders (TreeNode root) {
// write code here
if(root==null)//树为空
return null;
DLR(root);
int [][]res=new int[3][list1.size()];
for(int i=0;i<list1.size();i++){
res[0][i]=list1.get(i);
}
LDR(root);
for(int i=0;i<list2.size();i++){
res[1][i]=list2.get(i);
}
LRD(root);
for(int i=0;i<list3.size();i++){
res[2][i]=list3.get(i);
}
return res;
}
public void DLR(TreeNode root){//先序遍历
if(root==null)//树为空
return;
list1.add(root.val);
DLR(root.left);
DLR(root.right);
}
public void LDR(TreeNode root){//中序遍历
if(root==null)//树为空
return;
LDR(root.left);
list2.add(root.val);
LDR(root.right);
}
public void LRD(TreeNode root){//后序遍历
if(root==null)//树为空
return;
LRD(root.left);
LRD(root.right);
list3.add(root.val);
}
}
2.非递归解法（其实用栈模拟递归）
跟递归遍历的本质思路是一样的，按照根左右，左根右，左右根的顺序进行遍历，感觉后序遍历比较难，因为它需要左右子树，遍历完才遍历根结点，所以需要一个结点来记录上一个访问的结点，如果当前访问的结点，左右子树都为空就可以访问根结点了。时间复杂度：O（n），遍历所有的结点；空间复杂度：O（n），辅助空间栈。
import java.util.</integer></integer></integer>;

/*

  • public class TreeNode {
  • int val = 0;
  • TreeNode left = null;
  • TreeNode right = null;
  • }
  • /

public class Solution {
/**
*
* @param root TreeNode类 the root of binary tree
* @return int整型二维数组
*/
//用于存放每次遍历结果
List<integer> list1=new ArrayList<>();
List<integer> list2=new ArrayList<>();
List<integer> list3=new ArrayList<>();
public int[][] threeOrders (TreeNode root) {
// write code here
if(root==null)//树为空
return null;
DLR(root);
int [][]res=new int[3][list1.size()];
for(int i=0;i<list1.size();i++){
res[0][i]=list1.get(i);
}
LDR(root);
for(int i=0;i<list2.size();i++){
res[1][i]=list2.get(i);
}
LRD(root);
for(int i=0;i<list3.size();i++){
res[2][i]=list3.get(i);
}
return res;
}
public void DLR(TreeNode root){//先序遍历
if(root==null)//树为空
return;
TreeNode t=root;
Stack<treenode> s=new Stack<>();
while(t!=null||!s.empty()){
if(t!=null){
list1.add(t.val);//访问根子树
s.push(t);
t=t.left;//访问左子树
}else{
t=s.pop();
t=t.right;//访问右子树
}
}
}
public void LDR(TreeNode root){//中序遍历
if(root==null)//树为空
return;
TreeNode t=root;
Stack<treenode> s=new Stack<>();
while(t!=null||!s.empty()){
while(t!=null){
s.push(t);
t=t.left;//访问左子树
}
if(!s.empty()){
t=s.pop();
list2.add(t.val);//访问根结点
t=t.right;//访问右子树
}
}
}
public void LRD(TreeNode root){//后序遍历
if(root==null)//树为空
return;
TreeNode t=root;//当前访问结点
TreeNode pre=null;//上次访问结点
Stack<treenode> s=new Stack<>();
while(t!=null){//将当前结点移动到左子树的最下边
s.push(t);
t=t.left;//访问左子树
}
while(!s.empty()){
t=s.pop();
if(t.right!=null&&t.right!=pre){//该节点还有右子树
s.push(t);//把根结点压入栈
t=t.right;//访问右子树
while(t!=null){//到右子树的最左边
s.push(t);
t=t.left;
}
}else{//该节点即无右子树又无左子树
list3.add(t.val);//访问根结点
pre=t;//修改上次访问结点
}
}
}
}</treenode></treenode></treenode></integer></integer></integer>