首页 > 代码库 > 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?
思路:使用tag标记元素的左右子树是否已经输出完毕。若是,则输出该元素并将其出栈;否则,先遍历其左子树再遍历其右子树,同时修改tag值。
1 class StackNode 2 { 3 public: 4 StackNode():tag(true),node(0){} 5 StackNode( short aTag, TreeNode *aNode ):tag(aTag),node(aNode){} 6 short tag; 7 TreeNode *node; 8 }; 9 10 class Solution {11 public:12 vector<int> postorderTraversal(TreeNode *root) {13 vector<int> values;14 list<StackNode> stack;15 // root is empty.16 if( root == 0 ) { return values; }17 stack.push_back( StackNode( 1, root ) );18 19 // main loop.20 while( !stack.empty() ) {21 StackNode& sNode = stack.back();22 if( sNode.tag == 1 ) { // need to access left child.23 sNode.tag = 2;24 if( sNode.node->left ) {25 stack.push_back( StackNode( 1, sNode.node->left ) );26 }27 }28 else if( sNode.tag == 2 ) { // need to access right child.29 sNode.tag = 3;30 if( sNode.node->right ) {31 stack.push_back( StackNode( 1, sNode.node->right ) );32 }33 }34 else { // access current value.35 values.push_back( sNode.node->val );36 stack.pop_back();37 }38 }39 return values;40 }41 };
以下是网上看到的更加简洁的代码:(若上一个输出的元素是当前节点的左儿子或者右儿子,则说明已经完成了对其左右子树的遍历,输出当前节点并将其出栈;否则,将其左右儿子分别入栈。)
1 class Solution { 2 public: 3 vector<int> postorderTraversal(TreeNode *root) { 4 vector<int> ans; 5 list<TreeNode*> node_list; 6 if(root == NULL) return ans; 7 node_list.push_front(root); 8 TreeNode *head = root; 9 while(!node_list.empty())10 {11 TreeNode *cur = node_list.front();12 13 if(cur -> right == head || cur -> left == head || ((cur -> right == NULL) && (cur -> left == NULL)))14 {15 node_list.pop_front();16 ans.push_back(cur -> val);17 head = cur;18 }19 else20 {21 if(cur -> right != NULL) node_list.push_front(cur -> right);22 if(cur -> left != NULL) node_list.push_front(cur -> left);23 }24 }25 }26 };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。