来自leetcode原题
二叉树前序遍历、中序遍历、后续遍历
声明:
参考慕课的liuyubobobo老师的思路!!!老师太厉害了~
有别于教科书的经典非递归实现方式,本文采用模拟系统栈的方式实现非递归,目的是有助于理解递归与栈的紧密关系。并且,三种遍历的代码形式类似,而经典非递归在后序遍历部分较之前两者有很大差异且不易理解。
前序遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };
struct Commend{ string s; TreeNode* node; Commend(string s, TreeNode* node): s(s), node(node){} };
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> record; if(!root) return record;
stack<Commend> stack_Tree; stack_Tree.push(Commend("run", root));
while(!stack_Tree.empty()){ Commend commend = stack_Tree.top(); stack_Tree.pop(); if(commend.s == "print"){ record.push_back(commend.node->val); } else{ assert(commend.s == "run"); if(commend.node->right) stack_Tree.push(Commend("run", commend.node->right)); if(commend.node->left) stack_Tree.push(Commend("run", commend.node->left)); stack_Tree.push(Commend("print", commend.node)); } }
return record; } };
|
中序遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
| struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };
struct Commend{ string s; TreeNode* node; Commend(string s, TreeNode* node) : s(s), node(node) {} };
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> record; if(!root){ return record; }
stack<Commend> stack_Tree; stack_Tree.push(Commend("run", root));
while(!stack_Tree.empty()){ Commend commend = stack_Tree.top(); stack_Tree.pop();
if(commend.s == "print"){ record.push_back(commend.node->val); } else{ assert(commend.s == "run"); if(commend.node->right) stack_Tree.push(Commend("run", commend.node->right)); stack_Tree.push(Commend("print", commend.node)); if(commend.node->left) stack_Tree.push(Commend("run", commend.node->left)); } } return record; } };
|
后序遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };
struct Commend{ string s; TreeNode* node; Commend(string s, TreeNode* node) : s(s), node(node) {} };
class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> record; if(!root){ return record; }
stack<Commend> stack_Tree; stack_Tree.push(Commend("run", root));
while(!stack_Tree.empty()){ Commend commend = stack_Tree.top(); stack_Tree.pop();
if(commend.s == "print"){ record.push_back(commend.node->val); } else{ assert(commend.s == "run"); stack_Tree.push(Commend("print", commend.node)); if(commend.node->right) stack_Tree.push(Commend("run", commend.node->right)); if(commend.node->left) stack_Tree.push(Commend("run", commend.node->left)); } } return record; } };
|
参考链接
https://coding.imooc.com/class/82.html