目录

1.前序遍历

1.1传统的非递归前序遍历

1.2根据递归改来的

2.中序遍历

3.后序遍历

1.前序遍历

LeetCode《二叉树的前序遍历》

前序遍历有两种常见的，一种是传统的，类似于中序遍历

• 1.1传统的非递归前序遍历

/*** 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 *> stack;while (!stack.empty() || root) {if (root) {result.push_back(root->val);stack.push(root);root = root->left;} else {root = stack.top()->right;stack.pop();}}return result;}
};

• 1.2根据递归改来的

/*** 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;if (root) {stack<TreeNode *> stack;stack.push(root);while (!stack.empty()) {TreeNode *t = stack.top();stack.pop();result.push_back(t->val);if (t->right) {stack.push(t->right);}if (t->left) {stack.push(t->left);}}}return result;}
};

2.中序遍历

LeetCode《二叉树的中序遍历》

/*** 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) {vector<int> result;stack<TreeNode *> stack;while (!stack.empty() || root) {while (root) {stack.push(root);root = root->left;} if(!stack.empty()){result.push_back(stack.top()->val);root = stack.top()->right;stack.pop();}}return result;}
};

3.后序遍历

LeetCode《二叉树的后序遍历》

/*** 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> postorderTraversal(TreeNode *root) {vector<int> result;if (root) {stack<pair<TreeNode *, bool>> stack;stack.push(make_pair(root, false));while (!stack.empty()) {pair<TreeNode *, bool> top = stack.top();stack.pop();if (top.second) {result.push_back(top.first->val);} else {stack.push(make_pair(top.first, true));if (top.first->right) {stack.push(make_pair(top.first->right, false));}if (top.first->left) {stack.push(make_pair(top.first->left, false));}}}}return result;}
};