首页 > 代码库 > LeetCode "Binary Tree *-order Traversal' by Iteration
LeetCode "Binary Tree *-order Traversal' by Iteration
Binary Tree *-order traversal by recursion is trivial. But their iteration version deserves a look:
Pre-Order
class Solution { vector<int> ret;public: vector<int> preorderTraversal(TreeNode *p) { if (!p) return ret; stack<TreeNode *> stk; stk.push(p); while (!stk.empty()) { TreeNode *pTop = stk.top(); stk.pop(); ret.push_back(pTop->val); if (pTop->right) stk.push(pTop->right); if (pTop->left) stk.push(pTop->left); } return ret; }};
In-Order
class Solution {public: vector<int> inorderTraversal(TreeNode *root) { vector<int> ret; if (!root) return ret; unordered_set<TreeNode*> bk; stack<TreeNode *> stk; stk.push(root); while (!stk.empty()) { TreeNode *p = stk.top(); if (p->left && bk.find(p->left) == bk.end()) { stk.push(p->left); continue; } ret.emplace_back(p->val); stk.pop(); bk.insert(p); if (p->right) { stk.push(p->right); } } return ret; }};
Post-Order - DIFFICULT
class Solution {public: vector<int> postorderTraversal(TreeNode *root) { vector<int> ret; if (!root) return ret; // Init stack<TreeNode *> stk; stk.push(root); TreeNode *pPre = nullptr; // Go while (!stk.empty()) { TreeNode *pCurr = stk.top(); // Down: from parent to child if (!pPre || pPre->left == pCurr || pPre->right == pCurr) { if (pCurr->left) stk.push(pCurr->left); else if (pCurr->right) stk.push(pCurr->right); } // Up: from left child else if (pCurr->left == pPre) { if (pCurr->right) stk.push(pCurr->right); } // Up: from right child else { ret.push_back(pCurr->val); stk.pop(); } pPre = pCurr; } return ret; }};
LeetCode "Binary Tree *-order Traversal' by Iteration
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。