leetcode144.二叉樹的前序周遊（簡單）

基礎：遞歸解法

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

進階：遞推解法

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        /*非遞歸解法
        思路：一直向左，邊向左入棧同時push_back()
        root指向top()的right
        */
        vector<int> ans;
        stack<TreeNode *>st;
        while (!st.empty() || root != nullptr) {
            while (root != nullptr) {
                ans.push_back(root->val);
                st.push(root);
                root = root->left;
            }
            TreeNode* tmp = st.top();
            st.pop();  //容易忘！！！
            root = tmp->right;
        }
        return ans;
    }
};