Difficulty: Hard
Frequency: N/A
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?
My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> result; dfs(root, result); return result; } void dfs(TreeNode* node, vector<int>& result) { if (!node) return; dfs(node->left, result); dfs(node->right, result); result.push_back(node->val); } };
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:
[…] Binary Tree Postorder Traversal […]
LikeLike
[…] Binary Tree Postorder Traversal […]
LikeLike