NC45 实现二叉树先序，中序和后序遍历

vlambda
2021-08-08

NC45 实现二叉树先序，中序和后序遍历

情景提要

牛客题解系列，按照题号顺序开始。

NC45 实现二叉树先序，中序和后序遍历

题目描述

分别按照二叉树先序，中序和后序打印所有的节点。

输入输出示例

输入：

{1,2,3}

返回值：

[[1,2,3],[2,1,3],[2,3,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<vector<int> > threeOrders(TreeNode* root) { // write code here vector<vector<int>> res(3,vector<int>()); res[0] = preorder(root); res[1] = inorder(root); res[2] = postorder(root); return res; } vector<int> preorder(TreeNode* root){ stack<TreeNode*> st; vector<int> ret; if(root) st.push(root); while(!st.empty()){ TreeNode* node = st.top(); st.pop(); if(node){ if(node->right) st.push(node->right); if(node->left) st.push(node->left); st.push(node); st.push(nullptr); } else { TreeNode* tmp = st.top(); st.pop(); ret.push_back(tmp->val); } } return ret; } vector<int> inorder(TreeNode* root){ stack<TreeNode*> st; vector<int> ret; if(root) st.push(root); while(!st.empty()){ TreeNode* node = st.top(); st.pop(); if(node){ if(node->right) st.push(node->right); st.push(node); st.push(nullptr); if(node->left) st.push(node->left); } else { TreeNode* tmp = st.top(); st.pop(); ret.push_back(tmp->val); } } return ret; } vector<int> postorder(TreeNode* root){ stack<TreeNode*> st; vector<int> ret; if(root) st.push(root); while(!st.empty()){ TreeNode* node = st.top(); st.pop(); if(node){ st.push(node); st.push(nullptr); if(node->right) st.push(node->right); if(node->left) st.push(node->left); } else { TreeNode* tmp = st.top(); st.pop(); ret.push_back(tmp->val); } } return ret; }};

递归方法

** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: //前序遍历: 中左右 void travel(TreeNode * node,vector<int> &res){ if (node == NULL) return; res.push_back(node->val); travel(node->left,res); travel(node->right,res); } vector<int> preorderTraversal(TreeNode* root) { vector<int> result; //返回的结果 travel(root,result); return result; }};

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: //中序遍历 左中右 void travel(TreeNode* node,vector<int> &res){ if(node == NULL) return; travel(node->left,res); res.push_back(node->val); travel(node->right,res); } vector<int> inorderTraversal(TreeNode* root) { vector<int> result; travel(root,result); return result;  }};

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: //后序遍历 左右中 void travel(TreeNode* node,vector<int> &res){ if (node==NULL) return; travel(node->left,res); travel(node->right,res); res.push_back(node->val); } vector<int> postorderTraversal(TreeNode* root) { vector<int> result; travel(root,result); return result; }};

一般方法

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: //前序遍历: 中左右 // 先右后左，出栈顺序才会 左右 // 迭代法 vector<int> preorderTraversal(TreeNode* root) { vector<int> result; //返回的结果 stack<TreeNode*> st; st.push(root); while(!st.empty()){ TreeNode* tmp = st.top(); st.pop(); if(tmp!=NULL) result.push_back(tmp->val); else continue; st.push(tmp->right); st.push(tmp->left); } return result; }}

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: /* 中序遍历 左中右 迭代法 画出二叉树来模拟，思考 */ vector<int> inorderTraversal(TreeNode* root) { stack<TreeNode*> st; TreeNode* cur = root; vector<int> result; while(!st.empty()||cur!=nullptr){ if(cur!=nullptr){ st.push(cur); cur = cur->left; } else{ cur = st.top(); st.pop(); result.push_back(cur->val); cur = cur->right; } } return result; }};

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: //后序遍历 左右中 迭代法 // 1.中右左 (类似前序遍历) // 2.左右中 (再倒过来) vector<int> postorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> st; st.push(root); while(!st.empty()){ TreeNode* tmp = st.top(); st.pop(); if(tmp!=NULL) result.push_back(tmp->val); else continue; st.push(tmp->left); st.push(tmp->right); }  for(int i=0;i<result.size()/2;i++){ int temp = result[i]; result[i] = result[result.size()-i-1]; result[result.size()-i-1] = temp; }  return result; }};