144. Binary Tree Preorder Traversal
1. Description
Given the root of a binary tree, return the preorder traversal of its nodes' values.
2. Example
Example 1:
Input: root = [1,null,2,3]
Output: [1,2,3]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [1]
Output: [1]
Example 4:
Input: root = [1,2]
Output: [1,2]
Example 5:
Input: root = [1,null,2]
Output: [1,2]
3. Constraints
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
4. Follow Up
- Recursive solution is trivial, could you do it iteratively?
5. Solutions
My Accepted Solution(Follow Up)
n is the number of nodes in i_root
Time complexity: O(n)
Space complexity: O(n)
class Solution
{
public:
// vector<int> preorderTraversal(TreeNode* root)
vector<int> preorderTraversal(TreeNode *i_root)
{
vector<int> result;
if(i_root == nullptr) return result;
stack<TreeNode *> nodes;
nodes.push(i_root);
for(TreeNode *iter; !nodes.empty(); )
{
iter = nodes.top();
nodes.pop();
result.push_back(iter->val);
if(iter->right) nodes.push(iter->right);
if(iter->left) nodes.push(iter->left);
}
return result;
}
};
5.1 Stack(Follow Up)
n is the number of nodes in i_root
Time complexity: O(n)
Space complexity: O(n)
// use an assist node, this method could help use stack to finish preorder, midorder and postorder traversal
class Solution
{
public:
// vector<int> preorderTraversal(TreeNode* root)
vector<int> preorderTraversal(TreeNode *i_root)
{
vector<int> result;
if(i_root == nullptr) return result;
stack<TreeNode *> nodes;
for(auto iter = i_root; iter || !nodes.empty(); )
{
if(iter)
{
result.push_back(iter->val);
nodes.push(iter);
iter = iter->left;
}
else
{
iter = nodes.top();
nodes.pop();
iter = iter->right;
}
}
return result;
}
};