LeetCode二叉木の中序遍歴(最も詳しい解法!!)

二叉木を指定し、その中序遍歴を返します.
例:
入力:[1,null,2,3]1 2/3
出力:[1,3,2]ステップアップ:再帰アルゴリズムは簡単ですが、反復アルゴリズムで完成できますか?
解題構想:二叉木の中序遍歴:左根右.再帰的な考え方を採用するのは簡単だ.コードを直接見ましょう.
コード1:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
//         、   、 、   。
class Solution {
public:
     vector inorderTraversal(TreeNode *root) {
         vector res;
         inorder(root, res);
         return res;
     }
     void inorder(TreeNode *root, vector &res) {
         if (!root) 
             return;
         if (root->left) 
             inorder(root->left, res);
         res.push_back(root->val);
         if (root->right) 
             inorder(root->right, res);
     }
 };

コード2

class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
        if(root){
            inorderTraversal(root->left);
            res.push_back(root->val);
            inorderTraversal(root->right);
        }
        return res;
    }
private:
        vector res;
};

反復の解題構想1:ルートノードから、ルートノードをスタックに押し込んでから、左のサブノードをスタックに押し込み、スタックトップノードを取り出してノード値を保存し、現在のポインタを右のサブノードに移動し、右のサブノードが存在する場合は、次のループ時にすべての左のサブノードをスタックに押し込むことができます.これにより、アクセス順序が左-ルート-右になることが保証されます.

class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
        vector res;
        stack s;
        TreeNode *p = root;
        while (!s.empty() || p) {
            if (p) {
                s.push(p);
                p = p->left;
            } else {
                TreeNode *t = s.top(); s.pop();
                res.push_back(t->val);
                p = t->right;
            }
        }
        return res;
    }
};

反復的な問題解きの考え方2:個人的には考えがないほうがいいと思います.

class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
        vector res;
        stack s;
        TreeNode *p = root;
        while (!s.empty() || p) {
            if (p) {
                s.push(p);
                p = p->left;
            } 
            else {
                TreeNode *t = s.top(); 
                s.pop();
                res.push_back(t->val);
                p = t->right;
            }
        }
        return res;
    }
};

反復的な解題の構想3:Threaded binary treeを使って、アルゴリズムは以下の通りです:1.初期化ポインタcurはrootを指します.2.curが空でない場合、curに左サブノードがない場合、a)はcurの値を印刷する.b)curポインタをその右サブノードに向ける.逆にpreポインタをcurの左サブツリーの最も右のサブノードに向け,preに右のサブノードが存在しない場合a)はその右のサブノードをcurに戻す.b)curはその左サブノードを指す.逆に,a)preの右サブノードを空にする.b)curの値を印刷する.c)curポインタをその右サブノードに向ける.

class Solution {
public:
    vector inorderTraversal(TreeNode *root) {
        vector res;
        if (!root) return res;
        TreeNode *cur, *pre;
        cur = root;
        while (cur) {
            if (!cur->left) {
                res.push_back(cur->val);
                cur = cur->right;
            } else {
                pre = cur->left;
                while (pre->right && pre->right != cur) pre = pre->right;
                if (!pre->right) {
                    pre->right = cur;
                    cur = cur->left;
                } else {
                    pre->right = NULL;
                    res.push_back(cur->val);
                    cur = cur->right;
                }
            }
        }
        return res;
    }
};