给定一棵二叉树，分别按照二叉树先序，中序和后序打印所有的节点。
数据范围：
，树上每个节点的val值满足 
要求：空间复杂度 )
，时间复杂度
样例解释：
如图二叉树结构
[编程题]实现二叉树先序，中序和后序遍历
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
/**
* NC45 实现二叉树先序，中序和后序遍历
* @author d3y1
*/
public class Solution {
private ArrayList<Integer> list = new ArrayList<>();
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类 the root of binary tree
* @return int整型二维数组
*/
public int[][] threeOrders (TreeNode root) {
return solution1(root);
// return solution2(root);
}
/**
* 递归法
* @param root
* @return
*/
private int[][] solution1(TreeNode root){
run(root);
int n = list.size()/3;
int[][] results = new int[3][n];
for(int i=0; i<3; i++){
for(int j=0; j<n; j++){
results[i][j] = list.get(i*n+j);
}
}
return results;
}
/**
* 按序运行: 前序 -> 中序 -> 后序
* @param root
*/
private void run(TreeNode root){
preOrder(root);
inOrder(root);
postOrder(root);
}
/**
* 前序遍历
* @param root
*/
private void preOrder(TreeNode root){
if(root == null){
return;
}
list.add(root.val);
preOrder(root.left);
preOrder(root.right);
}
/**
* 中序遍历
* @param root
*/
private void inOrder(TreeNode root){
if(root == null){
return;
}
inOrder(root.left);
list.add(root.val);
inOrder(root.right);
}
/**
* 后序遍历
* @param root
*/
private void postOrder(TreeNode root){
if(root == null){
return;
}
postOrder(root.left);
postOrder(root.right);
list.add(root.val);
}
//////////////////////////////////////////////////////////////////////////////////////
/**
* 迭代法
* @param root
* @return
*/
private int[][] solution2(TreeNode root){
operate(root);
int n = list.size()/3;
int[][] results = new int[3][n];
for(int i=0; i<3; i++){
for(int j=0; j<n; j++){
results[i][j] = list.get(i*n+j);
}
}
return results;
}
/**
* 按序运行: 前序 -> 中序 -> 后序
* @param root
*/
private void operate(TreeNode root){
preorder(root);
inorder(root);
postorder(root);
}
/**
* 前序遍历: 栈
* @param root
* @return
*/
private void preorder(TreeNode root){
Stack<TreeNode> stack = new Stack<>();
if(root == null){
return;
}
stack.push(root);
TreeNode node;
while(!stack.isEmpty()){
node = stack.pop();
list.add(node.val);
if(node.right != null){
stack.push(node.right);
}
if(node.left != null){
stack.push(node.left);
}
}
}
/**
* 中序遍历: 栈
* @param root
* @return
*/
private void inorder(TreeNode root){
Stack<TreeNode> stack = new Stack<>();
TreeNode curr;
while(root!=null || !stack.isEmpty()){
// 最左边
while(root != null){
stack.push(root);
root = root.left;
}
curr = stack.pop();
list.add(curr.val);
root = curr.right;
}
}
/**
* 后序遍历: 栈
* @param root
* @return
*/
private void postorder(TreeNode root){
Stack<TreeNode> stack = new Stack<>();
TreeNode curr;
// 上次访问
TreeNode last = null;
while(root!=null || !stack.isEmpty()){
// 最左边
while(root != null){
stack.push(root);
root = root.left;
}
curr = stack.pop();
// 右节点为空或已访问
if(curr.right==null || curr.right==last){
// 访问当前节点
list.add(curr.val);
last = curr;
}
// 右节点非空且未访问
else{
// 当前节点再次入栈
stack.push(curr);
root = curr.right;
}
}
}
}
发表于 2025-01-26 13:20:29
回复(0)
不知道哪里有问题：
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类 the root of binary tree
* @return int整型二维数组
*/
public int[][] threeOrders (TreeNode root) {
// write code here
int[][] arr = new int[3][];
//先序
List<Integer> preList = new ArrayList<>();
preorder(root, preList);
//中序
List<Integer> inList = new ArrayList<>();
inorder(root, inList);
//后序
List<Integer> postList = new ArrayList<>();
postorder(root, postList);
//封装结果
int[] preArr = new int[preList.size()];
int[] inArr = new int[inList.size()];
int[] postArr = new int[postList.size()];
for(int i=0;i<preList.size();i++){
preArr[i] = preList.get(i);
}
for(int i=0;i<inList.size();i++){
inArr[i] = inList.get(i);
}
for(int i=0;i<postList.size();i++){
postArr[i] = postList.get(i);
}
arr[0] = preArr;
arr[1] = inArr;
arr[2] = postArr;
return arr;
}
public void preorder(TreeNode root, List<Integer> preList) {
if (root == null) {
return;
}
preList.add(root.val);
preorder(root.left, preList);
preorder(root.right, preList);
}
public void inorder(TreeNode root, List<Integer> preList) {
if (root == null) {
return;
}
preorder(root.left, preList);
preList.add(root.val);
preorder(root.right, preList);
}
public void postorder(TreeNode root, List<Integer> preList) {
if (root == null) {
return;
}
preorder(root.left, preList);
preorder(root.right, preList);
preList.add(root.val);
}
}
发表于 2023-10-04 22:38:15
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
int[][] travel = new int[3][];
/**
*
* @param root TreeNode类 the root of binary tree
* @return int整型二维数组
*/
public int[][] threeOrders (TreeNode root) {
// write code here
if(root==null)
{
return new int[3][0];
}
TreeNode cur = root;
//先序遍历
ArrayList<Integer> list = new ArrayList<>();
Pre(cur,list);
travel[0] = listToArr(list);
list.clear();//清空列表
cur = root;
In(cur,list);
travel[1] = listToArr(list);
list.clear();//清空列表
cur = root;
Last(cur,list);
travel[2] = listToArr(list);
list.clear();//清空列表
return travel;
}
//二叉树的先序遍历
public void Pre(TreeNode root,ArrayList<Integer> PreList)
{
if(root==null)
return;
PreList.add(root.val);
Pre(root.left,PreList);
Pre(root.right,PreList);
}
//二叉树的中序遍历
public void In(TreeNode root, ArrayList<Integer> InList)
{
if(root==null)
return;
In(root.left,InList);
InList.add(root.val);
In(root.right,InList);
}
//二叉树的后序遍历
public void Last(TreeNode root,ArrayList<Integer> LastList)
{
if(root==null)
return;
Last(root.left,LastList);
Last(root.right,LastList);
LastList.add(root.val);
}
//将list转换为数组
public int[] listToArr(ArrayList<Integer> list)
{
if(list!=null && list.size()!=0)
{
int[] arr = new int[list.size()];
int index = 0;
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext())
{
arr[index++] = iterator.next();
}
return arr;
}
return null;
}
}
发表于 2023-06-13 17:33:50
回复(0)
import java.util.*;
public class Solution {
public int[][] threeOrders (TreeNode root) {
int[][] resList = new int[3][];
List<Integer> list1 = new ArrayList<Integer>();
List<Integer> list2 = new ArrayList<Integer>();
List<Integer> list3 = new ArrayList<Integer>();
preOrder(root,list1);
inOrder(root,list2);
postOrder(root,list3);
resList[0] = new int[list1.size()];
resList[1] = new int[list2.size()];
resList[2] = new int[list3.size()];
for(int i=0;i<list1.size();i++){
resList[0][i] = list1.get(i);
resList[1][i] = list2.get(i);
resList[2][i] = list3.get(i);
}
return resList;
}
public void preOrder(TreeNode root,List<Integer> list){
if(root != null){
list.add(root.val);
preOrder(root.left,list);
preOrder(root.right,list);
}
}
public void inOrder(TreeNode root,List<Integer> list){
if(root != null){
inOrder(root.left,list);
list.add(root.val);
inOrder(root.right,list);
}
}
public void postOrder(TreeNode root,List<Integer> list){
if(root != null){
postOrder(root.left,list);
postOrder(root.right,list);
list.add(root.val);
}
}
}
发表于 2022-12-02 20:25:20
回复(0)
注意没值的时候，二维数组的长度是3，而不是0
import java.util.*;
public class Solution {
/**
*
* @param root TreeNode类 the root of binary tree
* @return int整型二维数组
*/
public int[][] threeOrders (TreeNode root) {
if(root==null){//没有元素
return new int[3][0];
}
ArrayList<Integer> firstList=new ArrayList<>();
ArrayList<Integer> secondList=new ArrayList<>();
ArrayList<Integer> thirdList=new ArrayList<>();
preTravel(firstList,root);
midTravel(secondList,root);
postTravel(thirdList,root);
int length=firstList.size();
int[][] arr=new int[3][length];
for(int i=0;i<length;i++){
arr[0][i]=firstList.get(i);
}
for(int i=0;i<length;i++){
arr[1][i]=secondList.get(i);
}
for(int i=0;i<length;i++){
arr[2][i]=thirdList.get(i);
}
return arr;
}
//前序遍历
public void preTravel(ArrayList<Integer> firstList,TreeNode root){
firstList.add(root.val);
if(root.left!=null){
preTravel(firstList,root.left);
}
if(root.right!=null){
preTravel(firstList,root.right);
}
}
//中序遍历
public void midTravel(ArrayList<Integer> secondList,TreeNode root){
if(root.left!=null){
midTravel(secondList,root.left);
}
secondList.add(root.val);
if(root.right!=null){
midTravel(secondList,root.right);
}
}
//后序遍历
public void postTravel(ArrayList<Integer> thirdList,TreeNode root){
if(root.left!=null){
postTravel(thirdList,root.left);
}
if(root.right!=null){
postTravel(thirdList,root.right);
}
thirdList.add(root.val);
}
}
发表于 2022-10-29 23:12:40
回复(0)
二叉树递归 --- 递归序 --- 前中后序遍历取决于你打算什么时候使用当前节点的值
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
class Solution{
/**
* 描述： 给定一棵二叉树，分别按照二叉树先序，中序和后序打印所有的节点。
*
* @param root TreeNode类 the root of binary tree
* @return int整型二维数组
*/
public int[][] threeOrders (TreeNode root) {
// write code here
ArrayList<Integer> path0 = new ArrayList<>();
ArrayList<Integer> path1 = new ArrayList<>();
ArrayList<Integer> path2 = new ArrayList<>();
orderDFS(root,path0,0);
orderDFS(root,path1,1);
orderDFS(root,path2,2);
int[][] res = new int[3][path0.size()];
for (int i = 0; i < path0.size(); i++) {
res[0][i] = path0.get(i);
res[1][i] = path1.get(i);
res[2][i] = path2.get(i);
}
return res;
}
public void orderDFS(TreeNode root, List<Integer> path, int order){
if (order!=0 && order!=1 && order != 2)
throw new RuntimeException("order must in [0,1,2]");
if (root == null) return;
int curVal = root.val;
if (order == 0)
path.add(curVal);
orderDFS(root.left,path,order);
if (order == 1)
path.add(curVal);
orderDFS(root.right,path,order);
if (order == 2)
path.add(curVal);
}
// static class TreeNode{
// int val = 0;
// TreeNode left = null;
// TreeNode right = null;
// }
}
发表于 2022-09-16 08:31:37
回复(0)
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整型二维数组
*/
public int[][] threeOrders (TreeNode root) {
// write code here
list.clear();
treeFirst(root);
arr = new int[3][list.size()];
appendStr(0);
treeCenter(root);
appendStr(1);
treeEnd(root);
appendStr(2);
return arr;
}
private int[][] arr;
private ArrayList<Integer> list = new ArrayList<>();
private void treeFirst(TreeNode tree) {
if (null != tree) {
list.add(tree.val);
treeFirst(tree.left);
treeFirst(tree.right);
}
}
private void treeCenter(TreeNode tree) {
if (null != tree) {
treeCenter(tree.left);
list.add(tree.val);
treeCenter(tree.right);
}
}
private void treeEnd(TreeNode tree) {
if (null != tree) {
treeEnd(tree.left);
treeEnd(tree.right);
list.add(tree.val);
}
}
private void appendStr(int index) {
for (int i = 0; i < list.size(); i++) {
arr[index][i] = list.get(i);
}
list.clear();
}
}
/*
* 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整型二维数组
*/
public int[][] threeOrders (TreeNode root) {
// write code here
list.clear();
treeFirst(root);
arr = new int[3][list.size()];
appendStr(0);
treeCenter(root);
appendStr(1);
treeEnd(root);
appendStr(2);
return arr;
}
private int[][] arr;
private ArrayList<Integer> list = new ArrayList<>();
private void treeFirst(TreeNode tree) {
if (null != tree) {
list.add(tree.val);
treeFirst(tree.left);
treeFirst(tree.right);
}
}
private void treeCenter(TreeNode tree) {
if (null != tree) {
treeCenter(tree.left);
list.add(tree.val);
treeCenter(tree.right);
}
}
private void treeEnd(TreeNode tree) {
if (null != tree) {
treeEnd(tree.left);
treeEnd(tree.right);
list.add(tree.val);
}
}
private void appendStr(int index) {
for (int i = 0; i < list.size(); i++) {
arr[index][i] = list.get(i);
}
list.clear();
}
}
发表于 2022-04-26 14:44:47
回复(0)
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整型二维数组
*/
public int[][] threeOrders (TreeNode root) {
if (root == null) {
return new int[3][0];
}
// write code here
int a[][] = new int[3][0];
List<Integer> list1 = new ArrayList();
List<Integer> list2 = new ArrayList();
List<Integer> list3 = new ArrayList();
printTree(root,list1,1);
printTree(root,list2,2);
printTree(root,list3,3);
a[0] = new int[list1.size()];
a[1] = new int[list2.size()];
a[2] = new int[list3.size()];
for (int i =0;i < list1.size();i++) {
a[0][i] = list1.get(i);
}
for (int i =0;i < list2.size();i++) {
a[1][i] = list2.get(i);
}
for (int i =0;i < list3.size();i++) {
a[2][i] = list3.get(i);
}
return a;
}
public void printTree(TreeNode root,List<Integer> list,int sort) {
if (sort == 1) {
list.add(root.val);
}
if (root.left != null) {
printTree(root.left,list,sort);
}
if (sort == 2) {
list.add(root.val);
}
if (root.right != null) {
printTree(root.right,list,sort);
}
if (sort == 3) {
list.add(root.val);
}
}
}
/*
* 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整型二维数组
*/
public int[][] threeOrders (TreeNode root) {
if (root == null) {
return new int[3][0];
}
// write code here
int a[][] = new int[3][0];
List<Integer> list1 = new ArrayList();
List<Integer> list2 = new ArrayList();
List<Integer> list3 = new ArrayList();
printTree(root,list1,1);
printTree(root,list2,2);
printTree(root,list3,3);
a[0] = new int[list1.size()];
a[1] = new int[list2.size()];
a[2] = new int[list3.size()];
for (int i =0;i < list1.size();i++) {
a[0][i] = list1.get(i);
}
for (int i =0;i < list2.size();i++) {
a[1][i] = list2.get(i);
}
for (int i =0;i < list3.size();i++) {
a[2][i] = list3.get(i);
}
return a;
}
public void printTree(TreeNode root,List<Integer> list,int sort) {
if (sort == 1) {
list.add(root.val);
}
if (root.left != null) {
printTree(root.left,list,sort);
}
if (sort == 2) {
list.add(root.val);
}
if (root.right != null) {
printTree(root.right,list,sort);
}
if (sort == 3) {
list.add(root.val);
}
}
}
发表于 2022-03-26 10:58:43
回复(1)
import java.util.ArrayList;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
ArrayList<Integer> list1 = new ArrayList<>();
ArrayList<Integer> list2 = new ArrayList<>();
ArrayList<Integer> list3 = new ArrayList<>();
/**
*
* @param root TreeNode类 the root of binary tree
* @return int整型二维数组
*/
public int[][] threeOrders (TreeNode root) {
// write code here
// 递归
preOrder(root);
inOrder(root);
postOrder(root);
int n = list1.size();
int[][] ans = new int[3][];
for(int i=0; i<3; i++) {
ArrayList<Integer> list;
switch(i) {
case 0: list = list1;break;
case 1: list = list2;break;
default: list = list3;break;
}
int[] temp = new int[n];
ans[i] = temp;
for(int j=0; j<n; j++) {
temp[j] = list.get(j);
}
}
return ans;
}
// 前序遍历
public void preOrder(TreeNode root) {
if (root == null) {
return;
}
list1.add(root.val);
preOrder(root.left);
preOrder(root.right);
}
// 中序遍历
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
list2.add(root.val);
inOrder(root.right);
}
// 后序遍历
public void postOrder(TreeNode root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
list3.add(root.val);
}
} import java.util.ArrayList;
import java.util.Stack;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
ArrayList<Integer> list1 = new ArrayList<>();
ArrayList<Integer> list2 = new ArrayList<>();
ArrayList<Integer> list3 = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>(); // 工具栈
/**
*
* @param root TreeNode类 the root of binary tree
* @return int整型二维数组
*/
public int[][] threeOrders (TreeNode root) {
// write code here
// 迭代
preOrder(root);
inOrder(root);
postOrder(root);
int n = list1.size();
int[][] ans = new int[3][];
for(int i=0; i<3; i++) {
ArrayList<Integer> list;
switch(i) {
case 0: list = list1;break;
case 1: list = list2;break;
default: list = list3;break;
}
int[] temp = new int[n];
ans[i] = temp;
for(int j=0; j<n; j++) {
temp[j] = list.get(j);
}
}
return ans;
}
// 前序遍历
// 前序遍历：类似层次遍历
public void preOrder(TreeNode root) {
if (root == null) {
return;
}
stack.clear();
stack.push(root);
while(!stack.isEmpty()) {
TreeNode curr = stack.pop(); // 此处直接pop，因为先序不用考虑回溯
list1.add(curr.val);
if (curr.right != null) { // 先入右孩子，再入左孩子，才能保证左孩子先出栈
stack.push(curr.right);
}
if (curr.left != null) {
stack.push(curr.left);
}
}
}
// 中序遍历
// 中序遍历：回溯算法
public void inOrder(TreeNode root) {
stack.clear();
TreeNode curr = root; // curr保存了当前需要处理的节点，而不是已经处理了的节点
while(curr != null || !stack.isEmpty()) {
if (curr != null) {
stack.push(curr); // 如果curr是正向遍历得到的，则需要保存到栈中，方便后续回溯
curr = curr.left; // 接下来需要处理左孩子
} else {
curr = stack.pop(); // 如果curr是反向回溯得到的，则需要将其值保存到结果集中
list2.add(curr.val);
curr = curr.right; // 接下来处理右孩子
}
}
}
// 后序遍历
// 后序遍历：回溯算法 + 层次遍历
public void postOrder(TreeNode root) {
if (root == null) {
return;
}
stack.clear();
stack.push(root);
TreeNode pre = null; // 指向上次访问的节点
while(!stack.isEmpty()) {
TreeNode curr = stack.peek();
// 如果当前节点是叶子节点、或者当前节点的左右孩子节点已经被访问过了，那么将当前节点值保存，并且回溯
if ((curr.left == null && curr.right == null) || (pre != null && (pre == curr.left || pre == curr.right))) {
list3.add(curr.val);
pre = curr;
stack.pop();
} else {
if (curr.right != null) {
stack.push(curr.right);
}
if (curr.left != null) {
stack.push(curr.left);
}
}
}
}
}
发表于 2022-02-26 15:17:42
回复(0)
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整型二维数组
*/
private int nodeNum=0;
private int preIndex=0;
private int inIndex=0;
private int postIndex=0;
public int[][] threeOrders (TreeNode root) {
// write code here
this.getNodeNum(root);
int res[][]=new int[3][nodeNum];
for(int i=0;i<3;i++){
res[i]=new int [nodeNum];
}
this.preOrder(res[0],root);
this.inOrder(res[1],root);
this.postOrder(res[2],root);
return res;
}
public void getNodeNum(TreeNode root){
if(root==null)
return;
nodeNum++;
getNodeNum(root.left);
getNodeNum(root.right);
}
public void preOrder(int res[],TreeNode root){
if(root==null)
return;
res[preIndex++]=root.val;
preOrder(res,root.left);
preOrder(res,root.right);
}
public void inOrder(int res[],TreeNode root){
if(root==null)
return;
inOrder(res,root.left);
res[inIndex++]=root.val;
inOrder(res,root.right);
}
public void postOrder(int res[],TreeNode root){
if(root==null)
return;
postOrder(res,root.left);
postOrder(res,root.right);
res[postIndex++]=root.val;
}
}
发表于 2022-02-17 16:44:46
回复(0)
import java.util.*;
public class Solution {
/**
*
* @param root TreeNode类 the root of binary tree
* @return int整型二维数组
*/
private int fistIndex = 0;
private int middleIndex = 0;
private int lastIndex = 0;
private int length;
public int[][] threeOrders (TreeNode root) {
// write code here
length(root);
int[][] res = new int[3][length];
int[] f = new int[length];
int[] m = new int[length];
int[] l = new int[length];
firstOrder(root,f);
middleOrder(root,m);
lastOrder(root,l);
res[0] = f;
res[1] = m;
res[2] = l;
return res;
}
public void firstOrder(TreeNode node,int[] res){
if(node == null)
return;
res[fistIndex++]=node.val;
firstOrder(node.left,res);
firstOrder(node.right,res);
}
public void middleOrder(TreeNode node,int[] res){
if(node == null)
return;
middleOrder(node.left,res);
res[middleIndex++]=node.val;
middleOrder(node.right,res);
}
public void lastOrder(TreeNode node,int[] res){
if(node == null)
return;
lastOrder(node.left,res);
lastOrder(node.right,res);
res[lastIndex++]=node.val;
}
public void length(TreeNode node){
if(node == null)
return;
length ++;
length(node.left);
length(node.right);
}
}
发表于 2022-01-21 14:52:56
回复(0)
请问各位大佬为啥我这句 return res.toArray(new int[res.size()][]);（就是我注释的那一句，list转数组，在牛客网就报错，在leetcode是可以用的，如果我想list<ArrayList>=转int[][],应该怎么写才规范呢？）
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
@SuppressWarnings("unchecked")
public class Solution {
/**
*
* @param root TreeNode类 the root of binary tree
* @return int整型二维数组
*/
ArrayList<List<Integer>> res=new ArrayList<List<Integer>>();
public int[][] threeOrders (TreeNode root) {
List<Integer> path=new ArrayList<Integer>();
preOrder(root,path);
res.add(new ArrayList(path));
path.clear();
inOrder(root,path);
res.add(new ArrayList(path));
path.clear();
postOrder(root,path);
res.add(new ArrayList(path));
// return res.toArray(new int[res.size()][]);
int[][]result=new int[3][path.size()];
for(int i=0;i<3;i++){
for(int j=0;j<path.size();j++){
result[i][j]=res.get(i).get(j);
}
}
return result;
}
void preOrder(TreeNode root,List<Integer> path){
if(root==null)
return;
path.add(root.val);
preOrder(root.left,path);
preOrder(root.right,path);
}
void inOrder(TreeNode root,List<Integer> path){
if(root==null)
return;
inOrder(root.left,path);
path.add(root.val);
inOrder(root.right,path);
}
void postOrder(TreeNode root,List<Integer> path){
if(root==null)
return ;
postOrder(root.left,path);
postOrder(root.right,path);
path.add(root.val);
}
}
发表于 2022-01-19 22:00:31
回复(0)
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整型二维数组
*/
public int[][] threeOrders (TreeNode root) {
// write code here
List<Integer> preList = new ArrayList();
List<Integer> midList = new ArrayList();
List<Integer> afterList = new ArrayList();
preOrder(root,preList);
midOrder(root,midList);
afterOrder(root,afterList);
int len=preList.size();
int [][]result=new int[3][len];
for(int i=0;i<len;i++){
result[0][i]=preList.get(i);
}
for(int i=0;i<len;i++){
result[1][i]=midList.get(i);
}
for(int i=0;i<len;i++){
result[2][i]=afterList.get(i);
}
return result;
}
//先序 中左右
public void preOrder(TreeNode root,List<Integer> list){
if(root==null){
return;
}
list.add(root.val);
preOrder(root.left,list);
preOrder(root.right,list);
}
//中序 左中右
public void midOrder(TreeNode root,List<Integer> list){
if(root==null){
return;
}
midOrder(root.left,list);
list.add(root.val);
midOrder(root.right,list);
}
//后序 左右中
public void afterOrder(TreeNode root,List<Integer> list){
if(root==null){
return;
}
afterOrder(root.left,list);
afterOrder(root.right,list);
list.add(root.val);
}
}
发表于 2021-12-28 15:46:37
回复(0)
一个递归方法搞定，取值的时机不同，就形成了遍历的不同，先序先取值，中序在中间，后序最后取值。
public class Solution {
public int[][] threeOrders (TreeNode root) {
ArrayList<Integer>arr1=new ArrayList<>();
ArrayList<Integer>arr2=new ArrayList<>();
ArrayList<Integer>arr3=new ArrayList<>();
first(root,arr1,arr2,arr3);
int[][] res = new int[3][arr1.size()];
for(int i = 0; i < arr1.size(); i++){
res[0][i] = arr1.get(i);
res[1][i] = arr2.get(i);
res[2][i] = arr3.get(i);
}
return res;
}
void first(TreeNode root,ArrayList<Integer> arr1,ArrayList<Integer> arr2,ArrayList<Integer> arr3){
if(root==null){
return;
}
arr1.add(root.val);
first(root.left,arr1,arr2,arr3);
arr2.add(root.val);
first(root.right,arr1,arr2,arr3);
arr3.add(root.val);
}
}
发表于 2021-12-15 14:47:29
回复(0)
public class Solution {
/**
*
* @param root TreeNode类 the root of binary tree
* @return int整型二维数组
*/
public int[][] threeOrders (TreeNode root) {
int [][] ans = new int [3][];
if (root == null) {
ans[0] = new int[]{};
ans[1] = new int[]{};
ans[2] = new int[]{};
return ans;
}
List<Integer> preSerial = new ArrayList<Integer>();
List<Integer> midSerial = new ArrayList<Integer>();
List<Integer> afterSerial = new ArrayList<Integer>();
preOrder(root, preSerial, midSerial, afterSerial);
int [] preArray = new int[preSerial.size()];
int [] midArray = new int[midSerial.size()];
int [] afterArray = new int[afterSerial.size()];
for (int i = 0; i < preSerial.size(); i++) {
preArray[i] = preSerial.get(i);
midArray[i] = midSerial.get(i);
afterArray[i] = afterSerial.get(i);
}
ans[0]= preArray;
ans[1]=midArray;
ans[2]=afterArray;
return ans;
}
private void preOrder(TreeNode node, List<Integer> nodes, List<Integer> midNodes, List<Integer> afterNodes) {
if (node == null) {
return;
}
nodes.add(node.val);
preOrder(node.left, nodes, midNodes,afterNodes);
midNodes.add(node.val);
preOrder(node.right, nodes,midNodes,afterNodes);
afterNodes.add(node.val);
}
}
发表于 2021-12-12 01:25:51
回复(0)
O和S双90以上
Java code：
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> order = new ArrayList<>();
public int[][] threeOrders (TreeNode root) {
// write code here
int[][] orders = new int[3][];
//adding pre order in orders
preOrderTrav(root);
int len = order.size();
int[] preOrder = new int[len];
orders[0] = addElementInArray(order,preOrder);
//clear the order list
order.clear();
//adding in order in orders
inOrderTrav(root);
int[] inOrder = new int[len];
orders[1] = addElementInArray(order,inOrder);
//clear the order list
order.clear();
//adding post order in orders
postOrderTrav(root);
int[] postOrder = new int[len];
orders[2] = addElementInArray(order,postOrder);
//clear the order list
order.clear();
return orders;
}
public void preOrderTrav(TreeNode root){
TreeNode node = root;
if(node != null){
order.add(node.val);
preOrderTrav(node.left);
preOrderTrav(node.right);
}
}
public void inOrderTrav(TreeNode root){
TreeNode node = root;
if(node != null){
inOrderTrav(node.left);
order.add(node.val);
inOrderTrav(node.right);
}
}
public void postOrderTrav(TreeNode root){
TreeNode node = root;
if(node != null){
postOrderTrav(node.left);
postOrderTrav(node.right);
order.add(node.val);
}
}
public int[] addElementInArray(List<Integer> list, int[] array){
for(int i = 0; i < array.length; i++){
array[i] = list.get(i);
}
return array;
}
}
发表于 2021-11-25 23:43:20
回复(0)
这题根本就不是在考察二叉树遍历，大部分时间实际上是在处理怎么把结果装到二维数组里。另外很多答案写了三个子函数，不是很能理解。
public class Solution {
public int[][] threeOrders (TreeNode root) {
int[][]temp = new int[3][0];
if (root == null) return temp;
ArrayList<Integer> first = new ArrayList<>();
ArrayList<Integer> mid = new ArrayList<>();
ArrayList<Integer> back = new ArrayList<>();
DFS(root, first, mid, back);
int[][] res = new int[3][first.size()];
for (int i = 0; i < first.size(); i++){
res[0][i] = first.get(i);
res[1][i] = mid.get(i);
res[2][i] = back.get(i);
}
return res;
}
void DFS(TreeNode root, ArrayList<Integer> first, ArrayList<Integer> mid,
ArrayList<Integer> back){
if (root == null)
return;
first.add(root.val);
DFS(root.left, first, mid, back);
mid.add(root.val);
DFS(root.right, first, mid, back);
back.add(root.val);
}
}
发表于 2021-11-18 15:41:35
回复(0)
public class Solution {
/**
*
* @param root TreeNode类 the root of binary tree
* @return int整型二维数组
*/
public int[][] threeOrders (TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> returnList = new ArrayList<>();
returnList.add(new ArrayList<Integer>());
returnList.add(new ArrayList<Integer>());
returnList.add(new ArrayList<Integer>());
firstOrder(root,returnList.get(0));
middleOrder(root,returnList.get(1));
lastOrder(root,returnList.get(2));
int[][] returnMatrix = new int[3][];
for(int i = 0; i < 3; i++){
returnMatrix[i] = new int[returnList.get(i).size()];
for(int j = 0 ; j < returnList.get(i).size(); j++){
returnMatrix[i][j] = returnList.get(i).get(j);
}
}
return returnMatrix;
}
public void firstOrder(TreeNode root,ArrayList<Integer> scanList){
if(root != null){
scanList.add(root.val);
firstOrder(root.left,scanList);
firstOrder(root.right,scanList);
}
}
public void middleOrder(TreeNode root,ArrayList<Integer> scanList){
if(root != null){
middleOrder(root.left,scanList);
scanList.add(root.val);
middleOrder(root.right,scanList);
}
}
public void lastOrder(TreeNode root,ArrayList<Integer> scanList){
if(root != null){
lastOrder(root.left,scanList);
lastOrder(root.right,scanList);
scanList.add(root.val);
}
}
}
发表于 2021-11-14 18:30:22
回复(0)
问题信息
难度：
61条回答
816收藏
17589浏览
通过挑战的用户
查看代码-
2023-03-14 14:38:13
-
2023-03-10 20:21:18
-
2023-03-04 16:37:51
-
2023-02-17 16:41:19
-
2023-01-07 22:03:13
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
