LeetCode - Binary Tree Postorder Traversal

发布时间:2017-2-27 10:21:06 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"LeetCode - Binary Tree Postorder Traversal",主要涉及到LeetCode - Binary Tree Postorder Traversal方面的内容,对于LeetCode - Binary Tree Postorder Traversal感兴趣的同学可以参考一下。

Binary Tree Postorder Traversal Given a binary tree, return the postorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3}, 1 \ 2 / 3 return [3,2,1]. Note: Recursive solution is trivial, could you do it iteratively? #include <iostream> #include <stack> #include <vector> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; struct sNode { TreeNode *pVal; bool doneLeft; bool doneRight; sNode(TreeNode *val) : pVal(val), doneLeft(false), doneRight(false) {} sNode() : pVal(NULL), doneLeft(false), doneRight(false) {} }; class Solution { public: vector<int> postorderTraversal(TreeNode* root) { if (!root) return vector<int>(); vector<int> result; stack<sNode> s; sNode traceNode = sNode(root); while (traceNode.pVal) { if (traceNode.pVal->left && !traceNode.doneLeft) { traceNode.doneLeft = true; s.push(traceNode); traceNode = sNode(traceNode.pVal->left); } else if (traceNode.pVal->right && !traceNode.doneRight) { traceNode.doneRight = true; s.push(traceNode); traceNode = sNode(traceNode.pVal->right); } else { result.push_back(traceNode.pVal->val); if (s.empty()) { traceNode = sNode(); } else { traceNode = s.top(); s.pop(); } } } return result; } }; int main() { TreeNode *head = new TreeNode(1); TreeNode *node1 = new TreeNode(2); TreeNode *node2 = new TreeNode(3); head->right = node1; node1->left = node2; Solution * ss = new Solution(); vector<int> res = ss->postorderTraversal(head); for (int i = 0; i < res.size(); ++i) { cout << res[i] << endl; } }

上一篇:Java 中的锁入门介绍
下一篇:获得Linux系统中的IP、MAC地址等信息

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。