144 Binary Tree Preorder Traversal¶

Given a binary tree, return the preorder traversal of its nodes’ values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3] Follow up: Recursive solution is trivial, could you do it iteratively?

Solution 1: Recursion¶

Time complexity: \(O(n)\) Space complexity: \(O(n)\)

class Solution {
public:
  vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ans;
    function<void(TreeNode*)> preorder = [&](TreeNode* n) {
      if (!n) return;
      ans.push_back(n->val);
      preorder(n->left);
      preorder(n->right);
    };
    preorder(root);
    return ans;
  }
};

Solution 2: Stack¶

Time complexity: \(O(n)\) Space complexity: \(O(n)\)

class Solution {
public:
  vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode*> s;
    if (root) s.push(root);
    while (!s.empty()) {
      TreeNode* n = s.top();
      ans.push_back(n->val);
      s.pop();
      if (n->right) s.push(n->right);
      if (n->left) s.push(n->left);
    }
    return ans;
  }