给定一棵二叉树,分别按照二叉树先序,中序和后序打印所有的节点。
数据范围:
,树上每个节点的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); } */ };
/** * 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; } };借用栈实现的非递归解法~
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; }
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); } }
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); } } }
# 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
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); } };
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); } }
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; } } };
/** * 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; } } } } };
递归遍历 + 迭代遍历
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
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); } }
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; }
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); } }
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); } }
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); } }看注释就行
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); } } } }