LeetCodeテーマの詳細-Binary Tree Preorder Traversal

タイトル:
Given a binary tree, return the preorder traversal of its nodes' values.
For example: Given binary tree  {1,#,2,3} ,

   1
    \
     2
    /
   3

return  [1,2,3] .
Note: Recursive solution is trivial, could you do it iteratively?
二叉木の遍歴は基礎問題であり、具体的には先序、中序と後序の問題に関連し、基本的な方法は再帰と非再帰があり、その中で非再帰の構想はまた使用スタックと使用スタックに分けられる.再帰的なメソッドコードは簡単ですが、オーバーヘッドが大きいので、ここでは表にしません.leetcode上の対応する問題に対してのみ非再帰的な2つの方法を与える.
一、使用スタック
ツリーの非再帰的なループは、スタックを使用してまだアクセスしていないノードを記録することを自然に連想します.スタックからpopが出るたびにノードにアクセスし、スタックが空になるまで右左サブツリー(順序が重要で右左)をスタックに押し込みます.コードは次のとおりです.

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

二、スタックを使用しない
スタックを使用する役割は、次にアクセスするノードをスタックで記録することであり、スタックを使用しない場合は、次にアクセスするノードを記録する他の方法を考えなければならない.Morrisは,ツリー自体の構造を変更して,次にアクセスするノードを記録し,アクセスが完了した後にツリーのノードを変更するように設計した.具体的には、現在アクセスするノードcurNodeについて、左サブツリーの最も右のノードtmp(左サブツリーがなければ不要)を見つけ、curNodeノードをtmpの右サブツリーに割り当てます.これにより,ツリー自体の構造を利用してアクセスが必要な情報を記録することができる.CurNodeの左サブツリーにアクセスした後、tmpの右サブツリーをNULLに割り当てて、ツリーの元の構造を復元します.コードは次のとおりです.

class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> valVec;
        TreeNode *p=root;
        if(!root)
            return valVec;
        while(p)
        {
            if(p->left==NULL)
            {
                valVec.push_back(p->val);
                p=p->right;
            }
            else
            {
                TreeNode *tmp=p->left;
                while(tmp->right && tmp->right !=p)
                {
                    tmp=tmp->right;
                }
                if(tmp->right==NULL)
                {
                    valVec.push_back(p->val);
                    tmp->right=p;
                    p=p->left;
                }
                else
                {
                    tmp->right=NULL;
                    p=p->right;
                }
            }
        }
    }
};

まだ理解しにくいと思ったら、次の図を見て理解を助けることができます.