首页 > 代码库 > 【leetcode】Binary Tree Postorder Traversal (hard) ☆
【leetcode】Binary Tree Postorder Traversal (hard) ☆
二叉树的后序遍历
用标记右子树vector的方法
vector<int> postorderTraversal(TreeNode *root) { vector<int> ans; vector<TreeNode *> stack; vector<bool> isRight; stack.push_back(root); isRight.push_back(false); TreeNode * pNode = NULL; while(!stack.empty()) { while((pNode = stack.back()) != NULL) { pNode = pNode->left; stack.push_back(pNode); isRight.push_back(false); } while(isRight.back() == true) { stack.pop_back(); isRight.pop_back(); ans.push_back(stack.back()->val); } stack.pop_back(); isRight.pop_back(); if(!stack.empty()) { pNode = stack.back(); stack.push_back(pNode->right); isRight.push_back(true); } } return ans; }
仅用一个栈的方法https://oj.leetcode.com/discuss/14118/post-order-traversal-using-two-satcks
vector<int> postorderTraversal(TreeNode *root) { stack<TreeNode *> st; vector<int> vRet; TreeNode *p, *pre = root; if (!root) return vRet; p = root->left; st.push(root); while (!st.empty() ) { while (p) { st.push(p); p = p->left; } p = st.top(); while (!p->right || pre==p->right) { vRet.push_back(p->val); pre = p; st.pop(); if (st.empty() ) break; p = st.top(); } p = p->right; } return vRet; }
【leetcode】Binary Tree Postorder Traversal (hard) ☆
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。