145. Binary Tree Postorder Traversal

Andreea
2 min readFeb 19, 2022

--

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.

--

--