首页 > 代码库 > Binary Tree Postorder Traversal
Binary Tree Postorder Traversal
先简单介绍下先序遍历、中序遍历和后序遍历，
先序遍历为ABC,中序遍历为BAC,后续遍历为BCA,根节点在的位置决定了什么遍历。
该题的递归解法：
class Solution {public: typedef TreeNode * STreeNode; vector<int> buf; vector<int> postorderTraversal(TreeNode *root) { if(root != NULL) rpostorder(root); return buf; } void rpostorder(TreeNode *root) { if(root->left == NULL && root->right == NULL) { buf.push_back(root->val); return ; } if(root->left != NULL) { rpostorder(root->left); } if(root->right != NULL) { rpostorder(root->right); } buf.push_back(root->val); } };该题的非递归解法：
class Solution {public: typedef TreeNode * STreeNode; vector<int> result; vector<int> postorderTraversal(TreeNode *root) { stack<pair<STreeNode,bool>> buf; if(root == NULL) return result; while(1) { if(root->left == NULL && root->right == NULL) { result.push_back(root->val); root = GetData(buf); if(root == NULL) break; } else if(root->left != NULL) { buf.push(pair<STreeNode,bool>(root,true)); if(root->right != NULL) { buf.push(pair<STreeNode,bool>(root->right,false)); } root = root->left; } else { buf.push(pair<STreeNode,bool>(root,true)); root = root->right; } } return result; } STreeNode GetData(stack<pair<STreeNode,bool>> &buf) { pair<STreeNode,bool> temp; if(buf.size() == 0) return NULL; while(1) { temp = buf.top(); buf.pop(); if(temp.second == false) break; result.push_back((temp.first)->val); if(buf.size() == 0) break; } if(temp.second == true) return NULL; else return temp.first; } };
Binary Tree Postorder Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。