Given the root of a binary tree, return the postorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3]
Output: [3,2,1]Example 2:
Input: root = []
Output: []Example 3:
Input: root = [1]
Output: [1]Example 4:
Input: root = [1,2]
Output: [2,1]Example 5:
Input: root = [1,null,2]
Output: [2,1]/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> v;
if(root == NULL){
return v;
}
postorder(root, v);
return v;
}
void postorder(TreeNode* root, vector<int> &v){
if(root == NULL){
return;
}
postorder(root->left, v);
postorder(root->right, v);
v.push_back(root->val);
}
};基本題，可以順便複習一下preorder, inorder，解法都一樣
Runtime: 4 ms, faster than 45.95% of C++ online submissions for Binary Tree Postorder Traversal.
Memory Usage: 8.6 MB, less than 13.56% of C++ online submissions for Binary Tree Postorder Traversal.
CSDN看到的解法，利用stack，潮到出水
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
TreeNode *p = root;
while (!s.empty() || p) {
if (p) {
s.push(p);
res.insert(res.begin(), p->val);
p = p->right;
} else {
TreeNode *t = s.top(); s.pop();
p = t->left;
}
}
return res;
}
};Runtime: 0 ms, faster than 100.00% of C++ online submissions for Binary Tree Postorder Traversal.
Memory Usage: 8.3 MB, less than 94.61% of C++ online submissions for Binary Tree Postorder Traversal.
