【LeetCode】144. Binary Tree Preorder Traversal

Question link

Link

Intuition

Given the root of a binary tree, return the preorder traversal of its nodes' values.
(給定一個二元樹的根，返回前序走訪過程中經過節點的數值)

經典的樹走訪問題，此題目共三種解法，羅列如下

1. Recursive
2. Stack
3. Null-Marked Iterative Traversal(不論Preorder、Inordere、Postorder都一樣的寫法)
   核心思想在當遇到要處理的節點時候，加入一個nullptr進行標記，之後如果遇到nullptr則就可以知道訪問到要處理的結點。

Approach

Complexity

• Time complexity:
  $O(n)$
• Space complexity:
  $O(1)$

Code

Solution 1 Recursive

class Solution {
public:
    void solve(vector<int>& v, TreeNode* root) {
        if (!root) return;
        v.push_back(root->val);    // mid
        solve(v, root->left);      // left
        solve(v, root->right);     // right
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        solve(ans, root);
        return ans;        
    }
};

Solution 2 Stack

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

Solution 3 Null-Marked Iterative Preorder Traversal

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