给定一棵二叉树，分别按照二叉树先序，中序和后序打印所有的节点。
数据范围：
，树上每个节点的val值满足 
要求：空间复杂度 )
，时间复杂度
样例解释：
如图二叉树结构
[编程题]实现二叉树先序，中序和后序遍历
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution
{
public:
/**
*
* @param root TreeNode类 the root of binary tree
* @return int整型vector<vector<>>
*/
vector<vector<int>> threeOrders(TreeNode *root)
{
// write code here
vector<vector<int>> result({{}, {}, {}});
visit(root, result);
return result;
/*
vector<int> a;
visit1(root,a);
result.push_back(a);
a.clear();
visit2(root,a);
result.push_back(a);
a.clear();
visit3(root,a);
result.push_back(a);
a.clear();
return result;
*/
}
void visit(TreeNode *root, vector<vector<int>> &a)
{
if (!root)
return;
a[0].push_back(root->val);
visit(root->left, a);
a[1].push_back(root->val);
visit(root->right, a);
a[2].push_back(root->val);
}
/*
void visit1(TreeNode *root, vector<int> &a)
{
if (!root)
return;
a.push_back(root->val);
visit1(root->left, a);
visit1(root->right, a);
}
void visit2(TreeNode *root, vector<int> &a)
{
if (!root)
return;
visit2(root->left, a);
a.push_back(root->val);
visit2(root->right, a);
}
void visit3(TreeNode *root, vector<int> &a)
{
if (!root)
return;
visit3(root->left, a);
visit3(root->right, a);
a.push_back(root->val);
}
*/
};
发表于 2022-02-21 14:50:22
回复(0)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类 the root of binary tree
* @return int整型vector<vector<>>
*/
vector<int> preOrder(TreeNode* root){
vector<int> res;
stack<TreeNode*> s;
s.push(root);
while(!s.empty()){
TreeNode* cur = s.top();
s.pop();
res.push_back(cur->val);
if(cur->right){
s.push(cur->right);
}
if(cur->left){
s.push(cur->left);
}
}
return res;
}
vector<int> inOrder(TreeNode* root){
vector<int> res;
stack<pair<TreeNode*,bool> > s;
s.push(make_pair(root,true));
while(!s.empty()){
TreeNode* cur = s.top().first;
if(s.top().second && cur->left){
s.top().second=false;
s.push(make_pair(cur->left, true));
continue;
}
res.push_back(cur->val);
s.pop();
if(cur->right){
s.push(make_pair(cur->right, true));
}
}
return res;
}
vector<int> postOrder(TreeNode* root){
vector<int> res;
stack<pair<TreeNode*,int> > s;
s.push(make_pair(root,1));//1为应该push left；2为应该push right；3为应该push_back val
while(!s.empty()){
TreeNode* cur = s.top().first;
if(s.top().second==1){
s.top().second++;
if(cur->left){
s.push(make_pair(cur->left, 1));
}
}else if(s.top().second==2){
s.top().second++;
if(cur->right){
s.push(make_pair(cur->right, 1));
}
}else{
s.pop();
res.push_back(cur->val);
}
}
return res;
}
vector<vector<int> > threeOrders(TreeNode* root) {
// write code here
vector<vector<int>> result;
result.push_back(preOrder(root));
result.push_back(inOrder(root));
result.push_back(postOrder(root));
return result;
}
};
借用栈实现的非递归解法~
发表于 2020-12-28 14:04:52
回复(1)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类 the root of binary tree
* @return int整型vector<vector<>>
*/
vector<int> v1;
void MLR(TreeNode* root){
if(!root)return;
v1.push_back(root->val);
MLR(root->left);
MLR(root->right);
}
void LMR(TreeNode* root){
if(!root)return;
LMR(root->left);
v1.push_back(root->val);
LMR(root->right);
}
void LRM(TreeNode* root){
if(!root)return;
LRM(root->left);
LRM(root->right);
v1.push_back(root->val);
}
vector<vector<int> > threeOrders(TreeNode* root) {
// write code here
//先实现先序遍历
vector<vector<int> > vv;
TreeNode* temp=root;
v1.clear();
MLR(temp);
vv.push_back(v1);
v1.clear();
LMR(temp);
vv.push_back(v1);
v1.clear();
LRM(temp);
vv.push_back(v1);
v1.clear();
return vv;
}
};
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类 the root of binary tree
* @return int整型vector<vector<>>
*/
vector<int> v1;
void MLR(TreeNode* root){
if(!root)return;
v1.push_back(root->val);
MLR(root->left);
MLR(root->right);
}
void LMR(TreeNode* root){
if(!root)return;
LMR(root->left);
v1.push_back(root->val);
LMR(root->right);
}
void LRM(TreeNode* root){
if(!root)return;
LRM(root->left);
LRM(root->right);
v1.push_back(root->val);
}
vector<vector<int> > threeOrders(TreeNode* root) {
// write code here
//先实现先序遍历
vector<vector<int> > vv;
TreeNode* temp=root;
v1.clear();
MLR(temp);
vv.push_back(v1);
v1.clear();
LMR(temp);
vv.push_back(v1);
v1.clear();
LRM(temp);
vv.push_back(v1);
v1.clear();
return vv;
}
};
发表于 2020-08-31 13:34:56
回复(0)
vector<vector<int> > threeOrders(TreeNode* root) {
vector<vector<int> > ans;
vector<int> preo,ino,pos;
stack<TreeNode*> st;
TreeNode * p=root;
/*“迭代方法，有点啰嗦“*/
while(p||!st.empty()){ //先序
if(p){
st.push(p);
preo.push_back(st.top()->val);
p=p->left;
}
else{
p=st.top();
st.pop();
p=p->right;
}
}
ans.push_back(preo);
TreeNode* q=root;
while(q||!st.empty()){ //中序
if(q){
st.push(q);
q=q->left;
}
else{
q=st.top();
ino.push_back(st.top()->val);
st.pop();
q=q->right;
}
}
ans.push_back(ino);
TreeNode* r=root;
while(r||!st.empty()){ //后序
if(r){
st.push(r);
pos.push_back(st.top()->val);
r=r->right;
}
else{
r=st.top();
st.pop();
r=r->left;
}
}
reverse(pos.begin(),pos.end());
ans.push_back(pos);
return ans;
}
发表于 2020-09-03 22:27:01
回复(2)
function threeOrders( root ) {
// write code here
let arr1 = [];
let arr2 = [];
let arr3 = [];
return [pre(root, arr1), mid(root, arr2), next(root, arr3)];
}
function pre(root, arr1){
if(root ==null) return root;
arr1.push(root.val)
pre(root.left, arr1)
pre(root.right, arr1)
return arr1
}
function mid(root, arr2){
if(root ==null) return root;
mid(root.left, arr2)
arr2.push(root.val)
mid(root.right, arr2)
return arr2
}
function next(root, arr3){
if(root ==null) return root;
next(root.left, arr3)
next(root.right, arr3)
arr3.push(root.val)
return arr3
}
module.exports = {
threeOrders : threeOrders
};
// write code here
let arr1 = [];
let arr2 = [];
let arr3 = [];
return [pre(root, arr1), mid(root, arr2), next(root, arr3)];
}
function pre(root, arr1){
if(root ==null) return root;
arr1.push(root.val)
pre(root.left, arr1)
pre(root.right, arr1)
return arr1
}
function mid(root, arr2){
if(root ==null) return root;
mid(root.left, arr2)
arr2.push(root.val)
mid(root.right, arr2)
return arr2
}
function next(root, arr3){
if(root ==null) return root;
next(root.left, arr3)
next(root.right, arr3)
arr3.push(root.val)
return arr3
}
module.exports = {
threeOrders : threeOrders
};
发表于 2021-08-28 16:02:16
回复(0)
递归处理
import java.util.*;
public class Solution {
List<Integer> pre = new ArrayList<>();
List<Integer> mid = new ArrayList<>();
List<Integer> last = new ArrayList<>();
public int[][] threeOrders (TreeNode root) {
dfs(root);
int n = pre.size();
int[][] res = new int[3][n];
for(int i=0;i<n;i++){
res[0][i] = pre.get(i);
res[1][i] = mid.get(i);
res[2][i] = last.get(i);
}
return res;
}
public void dfs(TreeNode root){
if(root==null) return;
pre.add(root.val);
dfs(root.left);
mid.add(root.val);
dfs(root.right);
last.add(root.val);
}
}
发表于 2021-03-16 10:40:10
回复(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
int[][] array = 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);
array[0] = new int[list1.size()];
array[1] = new int[list2.size()];
array[2] = new int[list3.size()];
for (int i = 0; i < list1.size(); ++i){
array[0][i] = list1.get(i);
array[1][i] = list2.get(i);
array[2][i] = list3.get(i);
}
return array;
}
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);
}
}
}
发表于 2021-08-31 19:59:01
回复(0)
Python
遇到树结构一般都可以从递归的思考方向入手
# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # # @param root TreeNode类 the root of binary tree # @return int整型二维数组 # class Solution: def mlr_dfs(self,root): if not root: return None self.result1.append(root.val) self.mlr_dfs(root.left) self.mlr_dfs(root.right) def lmr_dfs(self,root): if not root: return None self.lmr_dfs(root.left) self.result2.append(root.val) self.lmr_dfs(root.right) def rml_dfs(self,root): if not root: return None self.rml_dfs(root.left) self.rml_dfs(root.right) self.result3.append(root.val) def threeOrders(self , root ): # write code here result = [] self.result1 = [] self.mlr_dfs(root) result.append(self.result1) self.result2 = [] self.lmr_dfs(root) result.append(self.result2) self.result3 = [] self.rml_dfs(root) result.append(self.result3) return result # 简化一下就是评论区的简化版答案 # class Solution: # def threeOrders(self , root ): # # write code here # self.res = [[],[],[]] # self.dfs(root) # return self.res # def dfs(self,root): # if not root: return # self.res[0].append(root.val) # self.dfs(root.left) # self.res[1].append(root.val) # self.dfs(root.right) # self.res[2].append(root.val) # return
发表于 2021-04-30 15:44:46
回复(2)
个人觉得，代码，越简洁越好，越规律越好
class Solution {
public:
vector<vector<int> > threeOrders(TreeNode* root) {
vector<int> before;
vector<int> middle;
vector<int> after;
Before(root, before);
Middle(root,middle);
After(root, after);
vector<vector<int>> ans = {before,middle,after};
return ans;
}
void Before(TreeNode* root,vector<int>& before){
if(root==nullptr){
return;
}
before.push_back(root->val);
Before(root->left, before);
Before(root->right,before);
}
void Middle(TreeNode* root,vector<int>& before){
if(root==nullptr){
return;
}
Middle(root->left, before);
before.push_back(root->val);
Middle(root->right,before);
}
void After(TreeNode* root,vector<int>& before){
if(root==nullptr){
return;
}
After(root->left, before);
After(root->right,before);
before.push_back(root->val);
}
};
发表于 2021-12-03 17:53:32
回复(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整型二维数组
*/
int midIndex = 0;
int pre = 0;
int after = 0;
public int[][] threeOrders (TreeNode root) {
// write code here
//根据root节点个数创建int[][]
int count = 1;
int length = rootCount(root);
int[][] result = new int[3][length];
helper(root,result);
return result;
}
public int rootCount(TreeNode root){
if(root == null){
return 0;
}
return rootCount(root.left) + rootCount(root.right)+1;
}
public void helper(TreeNode root,int[][] result){
if(root == null){
return;
}
//中
result[0][pre++] = root.val;
helper(root.left,result);
result[1][midIndex++] = root.val;
helper(root.right,result);
result[2][after++] = root.val;
}
}
发表于 2021-08-29 11:48:02
回复(0)
递归处理。第一次遍历之后可以确定节点数，后续遍历可以一次性开辟足够的空间。
enum VisitMode {
kPre,
kIn,
kPost
};
class Solution {
public:
vector<vector<int>> threeOrders(TreeNode* root) {
vector<int> pre;
this->visit(root, VisitMode::kPre, pre);
vector<int> mid;
mid.reserve(pre.size());
this->visit(root, VisitMode::kIn, mid);
vector<int> post;
post.reserve(pre.size());
this->visit(root, VisitMode::kPost, post);
vector<vector<int>> result;
result.push_back(pre);
result.push_back(mid);
result.push_back(post);
return result;
}
const void visit(const TreeNode* root, const VisitMode mode, vector<int>& result) {
if (!root) {
return;
}
switch(mode) {
case VisitMode::kPre:
result.push_back(root->val);
this->visit(root->left, mode, result);
this->visit(root->right, mode, result);
break;
case VisitMode::kIn:
this->visit(root->left, mode, result);
result.push_back(root->val);
this->visit(root->right, mode, result);
break;
case VisitMode::kPost:
this->visit(root->left, mode, result);
this->visit(root->right, mode, result);
result.push_back(root->val);
break;
}
}
};
发表于 2021-07-25 16:52:38
回复(0)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类 the root of binary tree
* @return int整型vector<vector<>>
*/
// 递归就不说了
// void pre(TreeNode* root, vector<int>& rt) {
// if(!root) {
// return;
// }
// rt.push_back(root->val);
// pre(root->left, rt);
// pre(root->right, rt);
// }
// void middle(TreeNode* root, vector<int>& rt) {
// if(!root) {
// return;
// }
// middle(root->left, rt);
// rt.push_back(root->val);
// middle(root->right, rt);
// }
// void suf(TreeNode* root, vector<int>& rt) {
// if(!root) {
// return;
// }
// suf(root->left, rt);
// suf(root->right, rt);
// rt.push_back(root->val);
// }
// 非递归
vector<vector<int> > threeOrders(TreeNode* root) {
// write code here
vector<vector<int>> rt;
vector<int> pre_rt;
vector<int> middle_rt;
vector<int> suf_rt;
pre(root, pre_rt);
middle(root, middle_rt);
suf(root, suf_rt);
rt.push_back(pre_rt);
rt.push_back(middle_rt);
rt.push_back(suf_rt);
return rt;
}
// 前序遍历和中序遍历的唯一区别是：左边深入的时候访问还是，左边深入到头，再慢慢pop出来访问
void pre(TreeNode* root, vector<int>& rt) {
if(!root) {
return;
}
stack<TreeNode*> tmp;
TreeNode* cur = root;
while (!tmp.empty()||cur) {
while(cur) { // 个人习惯，喜欢一开始左边走到头
rt.push_back(cur->val);
tmp.push(cur);
cur = cur->left;
}
if (!tmp.empty()) {
cur = tmp.top();
tmp.pop();
cur = cur->right;
}
}
}
void middle(TreeNode* root, vector<int>& rt) {
if(!root) {
return;
}
stack<TreeNode*> tmp;
TreeNode* cur = root;
while (!tmp.empty()||cur) {
while(cur) { // 个人习惯，喜欢一开始左边走到头
tmp.push(cur);
cur = cur->left;
}
if (!tmp.empty()) {
cur = tmp.top();
rt.push_back(cur->val);
tmp.pop();
cur = cur->right;
}
}
}
void suf(TreeNode* root, vector<int>& rt) {
if(!root) {
return;
}
stack<TreeNode*> tmp;
TreeNode* cur = root;
TreeNode* lastVisit;
while (!tmp.empty()||cur) {
while(cur) { // 个人习惯，喜欢一开始左边走到头
tmp.push(cur);
cur = cur->left;
}
if (!tmp.empty()) {
cur = tmp.top();
// 访问根节点的条件
// 1.无右子树 或 2.右子树已经访问完毕
if (!cur->right || lastVisit == cur->right) {
rt.push_back(cur->val);
lastVisit = cur;
tmp.pop();
cur = NULL; // 不置为空，则 cur = tmp.top() 又会在下次 while 进入到栈里面，死循环
} else {
cur = cur->right;
}
}
}
}
};
发表于 2021-07-11 19:02:12
回复(0)
递归遍历 + 迭代遍历
class Solution:
def threeOrders(self, root):
# return self.recursive(root)
return self.iterate(root)
def recursive(self, root: TreeNode):
self.ans = [[], [], []]
self.preorder(root)
self.inorder(root)
self.postorder(root)
return self.ans
def preorder(self, root: TreeNode) -> None:
if not root:
return
self.ans[0].append(root.val)
self.preorder(root.left)
self.preorder(root.right)
def inorder(self, root: TreeNode) -> None:
if not root:
return
self.inorder(root.left)
self.ans[1].append(root.val)
self.inorder(root.right)
def postorder(self, root: TreeNode) -> None:
if not root:
return
self.postorder(root.left)
self.postorder(root.right)
self.ans[2].append(root.val)
def iterate(self, root):
return [self.preiter(root), self.initer(root), self.postiter(root)]
def preiter(self, root):
ans, stk = [], [root]
while stk:
root = stk.pop()
ans.append(root.val)
if root.right:
stk.append(root.right)
if root.left:
stk.append(root.left)
return ans
def initer(self, root):
ans, stk = [], []
while root or stk:
while root:
stk.append(root)
root = root.left
root = stk.pop()
ans.append(root.val)
root = root.right
return ans
def postiter(self, root):
ans, stk = [], [root]
while stk:
root = stk.pop()
ans.append(root.val)
if root.left:
stk.append(root.left)
if root.right:
stk.append(root.right)
ans.reverse()
return ans
发表于 2021-04-26 23:04: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整型二维数组
*/
List<Integer> list = new ArrayList<>();
List<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new ArrayList<>();
int i = 0, j = 0, k = 0;
public int[][] threeOrders (TreeNode root) {
search(root);
int[][] end = new int[3][list.size()];
for(int i = 0; i < list.size(); i++)
end[0][i] = list.get(i);
search1(root);
for(int i = 0; i < list1.size(); i++)
end[1][i] = list1.get(i);
search2(root);
for(int i = 0; i < list2.size(); i++)
end[2][i] = list2.get(i);
return end;
}
public void search(TreeNode root) {
if(root == null)
return;
list.add(root.val);
search(root.left);
search(root.right);
}
public void search1(TreeNode root) {
if(root == null)
return;
search1(root.left);
list1.add(root.val);
search1(root.right);
}
public void search2(TreeNode root) {
if(root == null)
return;
search2(root.left);
search2(root.right);
list2.add(root.val);
}
}
发表于 2021-04-24 21:43:36
回复(0)
使用JS来实现本题，使用的简单的递归方法。
三种遍历的简单实现很容易记，先序就在开头进行业务逻辑操作然后再递归左右子节点，中序就在递归左右子节点之间进行业务逻辑操作，后序就先进行递归然后再进行业务逻辑功能实现。
function first(root,arr){
if(root==null) return;
arr.push(root.val);
first(root.left,arr);
first(root.right,arr);
}
function mid(root,arr){
if(root==null) return;
mid(root.left,arr);
arr.push(root.val);
mid(root.right,arr);
}
function back(root,arr){
if(root==null) return;
back(root.left,arr);
back(root.right,arr);
arr.push(root.val);
}
function threeOrders( root ) {
// write code here
let arr1=[],arr2=[],arr3=[];
let ret=[];
first(root,arr1)
mid(root,arr2)
back(root,arr3)
ret.push(arr1);
ret.push(arr2);
ret.push(arr3);
return ret;
}
发表于 2021-04-03 15:22:51
回复(0)
import java.util.*;
public class Solution {
public ArrayList<Integer> first = new ArrayList<>();
public ArrayList<Integer> middle = new ArrayList<>();
public ArrayList<Integer> then = new ArrayList<>();
public int[][] threeOrders (TreeNode root) {
runOrder(root);
int[][] result ={
first.parallelStream().mapToInt(Integer::valueOf).toArray(),
middle.parallelStream().mapToInt(Integer::valueOf).toArray(),
then.parallelStream().mapToInt(Integer::valueOf).toArray()
};
return result;
}
public void runOrder(TreeNode root){
if(root==null){
return;
}
//前序
first.add(root.val);
runOrder(root.left);
//中序
middle.add(root.val);
runOrder(root.right);
//后续
then.add(root.val);
}
}
发表于 2021-03-12 17:19: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
ArrayList<Integer> pre = new ArrayList<Integer>();
ArrayList<Integer> in = new ArrayList<Integer>();
ArrayList<Integer> post = new ArrayList<Integer>();
preOrder(pre,root);//前序遍历
inOrder(in,root); //中序遍历
postOrder(post,root); //后序遍历
int[][] array = new int[3][pre.size()];
for(int i = 0; i < pre.size();i++){
array[0][i] = pre.get(i);
array[1][i] = in.get(i);
array[2][i] = post.get(i);
}
return array;
}
public static void preOrder(ArrayList<Integer> pre,TreeNode root){
if(root == null) return;
pre.add(root.val);
preOrder(pre,root.left);
preOrder(pre,root.right);
}
public static void inOrder(ArrayList<Integer> in,TreeNode root){
if(root == null) return;
inOrder(in,root.left);
in.add(root.val);
inOrder(in,root.right);
}
public static void postOrder(ArrayList<Integer> post,TreeNode root){
if(root == null) return;
postOrder(post,root.left);
postOrder(post,root.right);
post.add(root.val);
}
}
发表于 2021-03-10 11:34:57
回复(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 flag0 = 0, flag1= 0, flag2 = 0;
public int[][] threeOrders (TreeNode root) {
//声明返回数组：这里用一个函数来获取树的size
int[][] arr = new int[3][getTreeSize(root)];
//递归遍历：（三种递归在一个函数里就可以了）
travel(root, arr);
return arr; //返回答案
}
public void travel(TreeNode root, int[][] arr){
if(root==null){return;}
arr[0][flag0++] = (root.val);
travel(root.left, arr);
arr[1][flag1++] = (root.val);
travel(root.right, arr);
arr[2][flag2++] = (root.val);
}
public int getTreeSize(TreeNode root){
if(root==null){return 0;}
return 1+getTreeSize(root.left)+getTreeSize(root.right);
}
} 看注释就行
发表于 2021-03-08 15:49:36
回复(1)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
List<Integer> pre = new ArrayList<>();
int i = 0;
int[][] res;
public int[][] threeOrders(TreeNode root) {
preOrder(root);
res = new int[3][pre.size()];
for (Integer num : pre){
res[0][i ++] = num;
}
i = 0;
inOrder(root);
i = 0;
postOrder(root);
return res;
}
private void postOrder(TreeNode root) {
//使用栈的方式
Stack<TreeNode> st = new Stack<>();
TreeNode prev = null;
while (root != null || !st.isEmpty()){
while (root != null){
st.push(root);
root = root.left;
}
root = st.pop();
// 此时应该遍历右子树了
//如果右子树为空，或者右子树遍历完了,就该访问root节点了
if(root.right == null || root.right == prev){
res[2][i ++] = root.val;
prev = root;
//为了让栈能弹出下一个元素
root = null;
}else { //访问右孩子,并且需要把root重新入栈，因为此时root还没有被访问到
st.push(root);
root = root.right;
}
}
}
private void inOrder(TreeNode root) {
//使用栈的方式
Stack<TreeNode> st = new Stack<>();
while (root != null || !st.isEmpty()){
while (root != null){
st.push(root);
root = root.left;
}
root = st.pop();
res[1][i ++] = root.val;
root = root.right;
}
}
void preOrder(TreeNode root) {
//使用栈的方式遍历
Stack<TreeNode> st = new Stack<>();
st.push(root);
while (!st.isEmpty()){
TreeNode p = st.pop();
pre.add(p.val);
if(p.right != null){
st.push(p.right);
}
if(p.left != null){
st.push(p.left);
}
}
}
}
发表于 2021-03-02 15:30:51
回复(0)
问题信息
难度：
308条回答
797收藏
16986浏览
通过挑战的用户
查看代码-
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号
