94. Binary Tree Inorder Traversal（+树的遍历非递归）

题意：

非递归中序遍历。

树的先序遍历

vector<int> preorderTraversal(TreeNode* root) { stack<TreeNode*> s; vector<int> res; TreeNode *p = root; while (p || !s.empty()) { while (p) { s.push(p); //res.push_back(p->val); p = p->left; } if (!s.empty()) { p = s.top(); s.pop(); p = p->right; } } return res; }

中序遍历

vector<int> inorderTraversal(TreeNode* root) { stack<TreeNode*> s; vector<int> res; TreeNode *p = root; while (p || !s.empty()) { while (p) { s.push(p); p = p->left; } if (!s.empty()) { p = s.top(); res.push_back(p->val); s.pop(); p = p->right; } } return res; }

后序遍历

void PostOrder(TreeNode *root) { TreeNode *p = root, *r = NULL; stack<TreeNode*> s; while (p || !s.empty()) { if (p) {//走到最左边 s.push(p); p = p->left; } else { p = s.top(); if (p->right && p->right != r)//右子树存在，未被访问 p = p->right; else { s.pop(); visit(p->val); r = p;//记录最近访问过的节点 p = NULL;//节点访问完后，重置p指针 } }//else }//while }