ツリーの基本遍歴アルゴリズム

きほんデータこうぞう

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

ぜんじゅんかん遍歴

class Solution {
public:
 vector preorderTraversal(TreeNode *root)
    {
        vector visit;
        prevIterativeTraversal(root, visit);
        return visit;
    }
    
    void prevTraversal(TreeNode * root, vector &visit)
    {
        if(root == NULL)
            return;
        else
        {
            visit.push_back(root->val); 
            prevTraversal(root->left, visit);
            prevTraversal(root->right,visit);
        }
    }
    void prevIterativeTraversal(TreeNode *root, vector &visit)
    {
        stack nodeStack;
        TreeNode *iterator = root;
        TreeNode *prev = root;
        iterator = root;
        while(iterator != NULL || !nodeStack.empty())
        {
            while(iterator != NULL)            //           
            {
                prev = iterator;
                nodeStack.push(iterator);
                visit.push_back(iterator->val);
                iterator = iterator->left;
            }
            iterator = nodeStack.top();  //    
            nodeStack.pop(); 
            iterator = iterator->right;   //         
        }
    }
};

中順遍歴

class Solution {
public:
    vector midorderTraversal(TreeNode *root)
    {
        vector visit;
        midIterativeTraversal(root, visit);
        return visit;
    }

    void midTraversal(TreeNode * root, vector &visit)
    {
        if(root == NULL)
            return;
        else
        {
            midTraversal(root->right,visit);
            visit.push_back(root->val); 
            midTraversal(root->left, visit);
        }
    }
    void midIterativeTraversal(TreeNode *root, vector &visit)
    {
        stack nodeStack;
        TreeNode *iterator = root;
        TreeNode *prev = root;
        iterator = root;
        while(iterator != NULL || !nodeStack.empty())  
        {
            while(iterator != NULL)     
            {
                prev = iterator;
                nodeStack.push(iterator);
                iterator = iterator->left;
            }
            iterator = nodeStack.top();
            visit.push_back(iterator->val);    //                    
            nodeStack.pop();
            iterator = iterator->right;
        }
    }
};

後段遍歴

class Solution {
public:
    vector postorderTraversal(TreeNode *root)
    {
        vector visit;
        postIterativeTraversal(root, visit);
        return visit;
    }
    void postTraversal(TreeNode * root, vector &visit)
    {
        if(root == NULL)
            return;
        else
        {
            postTraversal(root->left, visit);
            postTraversal(root->right,visit);
            visit.push_back(root->val); 
        }
    }
    void postIterativeTraversal(TreeNode *root, vector &visit)
    {
        stack nodeStack;
        TreeNode *iterator = root;
        TreeNode *prev = root;
        iterator = root;
        while(iterator != NULL || !nodeStack.empty())
        {
            while(iterator != NULL)           //        ,           
            {
                prev = iterator;
                nodeStack.push(iterator);
                iterator = iterator->left;
            }
            prev = iterator;
            iterator = nodeStack.top();     
            while (iterator->right == prev)   //                  
            {
                nodeStack.pop();            
                visit.push_back(iterator->val);     //                  
                if(nodeStack.empty())
                    return;
                prev = iterator;
                iterator = nodeStack.top();
            }
            prev = iterator;
            iterator = iterator->right;

        }
    }
};

階層遍歴

class Solution {
public:
    vector levelorderTraversal(TreeNode *root)
    {
        vector visit;
        queue nodeQueue;
        TreeNode *iterator = NULL;
        if(root != NULL)
            nodeQueue.push(root);
        while (!nodeQueue.empty())
        {
            iterator = nodeQueue.front();
            nodeQueue.pop();
            visit.push_back(iterator->val);
            if (iterator->left != NULL)
                nodeQueue.push(iterator->left);
            if (iterator->right != NULL)
                nodeQueue.push(iterator->right);

        }
        return visit;
    }
};