# 145. Binary Tree Postorder Traversal

--

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);    }};`

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.