LeetCode144. ツリーの前順遍歴

二叉木の前順遍歴には主に2つの方法があります.
1.再帰的な実装:

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

2.非再帰的実現:

class Solution {
public:
    vector preorderTraversal(TreeNode* root) {
        vector ans;
        if(root==NULL)
            return ans;
        preorder(ans,root);
        return ans;
    }
    
    void preorder(vector& ans,TreeNode* root){
        stack s;
        while(!s.empty() || root!=NULL){
            while(root!=NULL){
                ans.push_back(root->val);
                s.push(root);
                root = root->left;
            }
            if(!s.empty()){
                root = s.top();
                s.pop();
                root = root->right;
            }
        }
    }
};

簡単に考えてみましょう.ルートノードが空でない場合、ルートノードにアクセスし、スタックに組み込みます.ルートノードの左サブツリーが空でない場合は、左ノードをルートノードに設定します.空の場合は、スタックトップ要素を取り、スタックトップ要素の右ノードをルートノードとしてスタックが空でrootが空になるまで配置します.