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?
vector<int> postorderTraversal(TreeNode *root){ vector<int> res; if(root == NULL) return res; stack<TreeNode *> record; record.push(root); TreeNode *pre = NULL; while(!record.empty()){ TreeNode *node = record.top(); if((node->left == NULL && node->right == NULL)||(pre!=NULL &&(pre == node->left || pre == node->right)) ){ res.push_back(node->val); record.pop(); pre = node; }else{ if(node->right) record.push(node->right); if(node->left ) record.push(node->left); } } return res; }
另一种方法：
通过不断的交换左右孩子，然后压栈，最后弹出，即可得到结果
时间复杂度为O(h),h为树的高度，空间复杂度为O(n)
vector<int> postorderTraversa(TreeNode *root){ vector<int> res; if(root == NULL) return res; stack<TreeNode *> post_record,reverse_record; post_record.push(root); while(!post_record.empty()){ TreeNode *node = post_record.top(); reverse_record.push(node); post_record.pop(); if(node->left) post_record.push(node->left); if(node->right) post_record.push(node->right); } while(!reverse_record.empty()){ res.push_back(reverse_record.top()->val); reverse_record.pop(); } return res; }
Leetcode Binary Tree Postorder Traversal,布布扣,bubuko.com
Leetcode Binary Tree Postorder Traversal
原文：http://www.cnblogs.com/xiongqiangcs/p/3795531.html