題69~71:二叉木の階層遍歴

16256 ワード

1.タイトルの説明
与えられた一課二叉木(以下)は、上から下へ、下から上へ、Z字形を上から下へ、4/2 6///1 3 5 7の出力結果を以下のように完成する.第1のケース:上から下へ、[4],[2,6],[1,3,5,7]]第2のケース:下から上へ、[2,6],[4]第3のケース:Z字形が上から下へ階層的に遍歴する:[[4],[6,2],[1,3,5,7]]
2.ツリーのデータ構造:

struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int v = 0, TreeNode *l = NULL, TreeNode *r = NULL):val(v),left(l),right(r){}
};

3.上から下へ移動
3.1構想分析
「剣指offer」にはこれと似たようなテーマがあります.それは階層が二叉樹を遍歴しているだけで、各層のノードを単独で置くことは要求されていません.ノードを印刷するたびに、ノードにサブノードがある場合は、そのノードのサブノードをキューの末尾に配置します.次に、キューのヘッダに最も早くキューに入ったノードを取り出します.キュー内のすべてのノードが印刷されるまで、前の印刷操作を繰り返します.しかし、本題が少し複雑なのは、各層の数を分けて2次元ベクトルに保存することですが、基本的には同じ考えです.まず、キューを作成し、ルートノードを入れてから、ルートノードの左右の2つのサブノードを探して、ルートノードを削除します.このとき、キューの要素は次のレベルのすべてのノードで、1つのforでループして、1つの1次元ベクトルに保存します.ループした後、この1次元ベクトルを2次元ベクトルに保存します.レイヤシーケンスのループを完了できます.
3.2方法1:反復法

vector<vector<int>> levelOrder(TreeNode *root)
    {
        vector<vector<int>> result;
        if(root == NULL)
        {
            return result;
        }
        queue q;
        q.push(root);
        while(!q.empty())
        {
            vector<int> oneLevel;
            int size = q.size();
            for(int i = 0; i < size; i++)
            {
                TreeNode *node = q.front();
                q.pop();
                oneLevel.push_back(node->val);
                if(node->left != NULL)
                {
                    q.push(node->left);
                }
                if(node->right != NULL)
                {
                    q.push(node->right);
                }
            }
            result.push_back(oneLevel);
        }
        return result;
}

3.3方法2:再帰法
再帰の核心は、2次元配列と変数levelが必要です.levelが前のレイヤの個数に再帰されると、空のレイヤを新規作成し、数字を追加し続けます.

vector<vector<int>> levelOrder(TreeNode *root)
{
    vector<vector<int>> result;
    traverse(root, 0, result);
    return result;
}
void traverse(TreeNode *root, size_t level, vector<vector<int>> &result)
    {
        if(root == NULL)
        {
            return;
        }
        if(result.size() == level)
        {
            result.push_back(vector<int>());
        }
        result[level].push_back(root->val);
        if(root->left != NULL)
        {
            traverse(root->left, level+1, result);
        }
         if(root->right != NULL)
        {
            traverse(root->right, level+1, result);
        }
}

4.下から上へ
4.1考え方分析
この場合は上記の場合と一致し,最後の出力順序が異なる点で異なる.
4.2方法1:反復法

vector<vector<int>> levelOrderBottom(TreeNode* root) 
   {
        vector<vector<int> > result;
        if(root == NULL)
        {
            return result;
        }
        queue q;
        q.push(root);
        while(!q.empty())
        {
            vector<int> oneLevel;
            int size = q.size();
            for(int i = 0; i < size; i++)
            {
                TreeNode *node = q.front();
                q.pop();
                oneLevel.push_back(node->val);
                if(node->left != NULL)
                {
                    q.push(node->left);
                }
                if(node->right != NULL)
                {
                    q.push(node->right);
                }
            }
            result.insert(result.begin(), oneLevel);
        }
        return result;
    }

4.3方法2:再帰法

vector<vector<int>> levelOrderBottom(TreeNode* root) 
   {
        vector<vector<int> > result;
        levelorder(root, 0, result);
        return vector<vector<int> > (result.rbegin(), result.rend());
    }
    void levelorder(TreeNode *root, int level, vector<vector<int> > &result)
    {
        if (root == NULL)
        {
            return;
        }
        if (result.size() == level)
        {
            result.push_back({});
        }
        result[level].push_back(root->val);
        if (root->left) 
        {
            levelorder(root->left, level + 1, result);
        }
        if (root->right) 
        {
            levelorder(root->right, level + 1, result);
        }
}

5.ジグザグを上から下へ移動
5.1構想分析
この問題は以前の階層遍歴の変形で、違いは1行が左から右へ遍歴し、次の行が右から左へ遍歴し、交差往復の字形の層序遍歴である.その特徴に基づいて、私たちはスタックの後進先出の特徴を使って、この問題は私たちが2つのスタックを維持して、隣接する2行はそれぞれ2つのスタックの中に保存して、スタックの順序も異なっていて、1つのスタックは先進的な左サブノードでそれから右サブノードで、もう1つのスタックは先進的な右サブノードでそれから左サブノードで、このようにスタックの順序は私たちが望んでいる字形です.
5.2方法1:反復法(ダブルスタック実装)

vector<vector<int>> zigzagLevelOrder(TreeNode *root) 
    {
        vector<vector<int>> result;
        if(root == NULL)
        {
            return result;
        }
        stack s1;
        stack s2;
        s1.push(root);
        vector<int> out; //        
        while(!s1.empty() || !s2.empty())
        {
            while(!s1.empty())
            {
                TreeNode *pCur = s1.top();
                s1.pop();
                out.push_back(pCur->val);
                if(pCur->left != NULL)
                {
                    s2.push(pCur->left);
                }
                if(pCur->right != NULL)
                {
                    s2.push(pCur->right);
                }
            }
           if(!out.empty())
            {
                result.push_back(out);
            }
            out.clear();
            while(!s2.empty())
            {
                TreeNode *pCur = s2.top();
                s2.pop();
                out.push_back(pCur->val);
                if(pCur->right != NULL)
                {
                    s1.push(pCur->right);
                }
                if(pCur->left)
                {
                    s1.push(pCur->left);
                }
            }
            if(!out.empty())
            {
                result.push_back(out);
            }
            out.clear();
        }
        return result;
}

5.3方法2:反復法(キュー実装)

vector<vector<int>> zigzagLevelOrder2(TreeNode *root) //    Z      
    {
        vector<vector<int>> result;
        if(root == NULL)
        {
            return result;
        }
        queue q;
        bool left_to_right = true; //             ，          
        vector<int> out; //        

        q.push(root);
        q.push(nullptr);
        while(!q.empty())
        {
            TreeNode *pCur = q.front();
            q.pop();
            if(pCur != NULL)
            {
                out.push_back(pCur->val);
                if(pCur->left != NULL)
                    q.push(pCur->left);
                if(pCur->right != NULL)
                    q.push(pCur->right);
            }
            else
            {
                if(left_to_right)
                {
                    result.push_back(out);
                }
                else
                {
                    reverse(out.begin(), out.end());
                    result.push_back(out);
                }
                out.clear();
                left_to_right = !left_to_right ;
                if(q.size() > 0)
                    q.push(nullptr);
            }
        }
        return result;
}

5.4方法3:再帰法(キュー実装)

    vector<vector<int> > zigzagLevelOrder3(TreeNode *root)  
        vector<vector<int>> result;
        recursive (root, 1, result, true); 
        return result;
    }

    void recursive(TreeNode *root, size_t level, vector<vector<int>> &result, bool left_to_right)
    {
        if (!root) 
            return;

        if (level > result.size())
            result.push_back(vector<int>());

        if (left_to_right)
            result[level-1].push_back(root->val);
        else
            result[level-1].insert(result[level-1].begin(), root->val);

        recursive (root->left, level+1, result, !left_to_right);
        recursive (root->right, level+1, result, !left_to_right);
}

ps:完全なテストコードは私のコードシートを参照してください.https://code.csdn.net/snippets/1762076
参考記事:1、http://www.cnblogs.com/grandyang/p/4051321.html 2、http://www.cnblogs.com/grandyang/p/4051326.html 3、http://www.cnblogs.com/grandyang/p/4297009.html4、Acmの家:Binary Tree Zigzag Level Order Traversal
Note:以上の文章は私の文章を書くのに大きな役割を果たしました.ここで感謝します.

【MySQL】ロックと独立性レベル

MySQL MERGEストレージエンジンの概要