LeetCode Binary Tree Postorder Traversal

1.题目

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?

2.解决方案1class Solution {public:vector<int> postorderTraversal(TreeNode *root) {vector<int> res;if(root == NULL){return res;}stack<TreeNode*> stackNode;stackNode.push(root);TreeNode* preNode = NULL;while(stackNode.empty() == false){TreeNode* curNode = stackNode.top();bool isLeafNode = curNode->left == NULL && curNode->right == NULL;if(isLeafNode || (preNode != NULL && (preNode == curNode->left || preNode == curNode->right))){res.push_back(curNode->val);stackNode.pop();preNode = curNode;}else{if(curNode->right != NULL){stackNode.push(curNode->right);}if(curNode->left != NULL){stackNode.push(curNode->left);}}}return res;}};思路：非递归的方式要用stack来辅助。

关键点1：

我们知道stack是先进的后出，而后序遍历是要先访问左节点，所以我们要先把右节点push到stack中，再push左节点。

关键点2：

叶子可以直接输出了，但如果一个节点有左右一个节点，也是要输出的，输出的时机是这题的难点。这里又增加了一个变量，，来记录之前输出的点，假如一个节点的左右叶子节点有一个输出了，然后再访问到这个节点，因为stack的特性，说明左右节点都已经输出了，说明这个时候就可以输出这个根节点了。

3.解决方案2

class Solution {public:vector<int> result;void HXBL(TreeNode* root){if(root == nullptr)return;if(root->left != NULL){HXBL(root->left);}if(root->right != NULL){HXBL(root->right);}if(root != NULL){result.push_back(root->val);}}vector<int> postorderTraversal(TreeNode *root) {result.clear();HXBL(root);return result;}};递归当然简单了，就是慢。慢就是bug。

仿佛松树就是一位威风的将军，守护着国家的国民。