[C++]LeetCode:102 Flatten Binary Tree to Linked List(ツリー回転前シーケンスチェーンテーブル)

タイトル:
Given a binary tree, flatten it to a linked list in-place.
For example, Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

click to show hints.
Hints:
If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.
Answer 1:再帰法
考え方:テーマ変換の過程を観察して、私たちは前の順序でチェーンテーブルに接続しましたが、チェーンテーブルは木の構造で、ずっと右へ(子供をしていません)チェーンテーブルをシミュレートします.ノード間のリンクを保証するために、最初にループした前のノードpreを維持し、preの左ノードを空にするたびに、右ノードを現在のノード(すなわち、順にループする順序)に設定します.ここでは、右の子供ノードsavedRightをメンテナンスして、再帰を容易にする必要があります.そうでないと、現在のノードの右ノードが上書きされ、後ろに取り出せない可能性があります.
ツリーの再帰方法は,主に再帰終了条件と再帰条件を考慮し,再帰がツリーの構造を修正する場合は,ノードを保存する必要がある.
Attention:
1.前のノードpre、現在のノードの右の子ノードsavedRightの順に2つのノードを維持します.右の子供ノードのリンクと保護を容易にします.

private:
    TreeNode* pre = NULL;   //           ，          pre 

 TreeNode* savedRight = root->right;

2. リンクプロセスに注意して、私たちはpreの左の子供を空にして、右の子供を現在のノードにして、前の順序のチェーンテーブルのリンクを実現します.

if(pre != NULL)
        {
            pre->left = NULL; //          
            pre->right = root; //          root
        }

3.root->left再帰、次にメンテナンスの右ノード再帰savedRightの順に注意してください.preは常に維持されます.

 pre = root;
 flatten(root->left);
 flatten(savedRight); //       ，              

複雑度:O(N)
AC Code:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode *root) {
        if(root == NULL) return;
        TreeNode* savedRight = root->right;
        
        if(pre != NULL)
        {
            pre->left = NULL; //          
            pre->right = root; //          root
        }
        pre = root;
        flatten(root->left);
        flatten(savedRight); //       ，              
    }

private:
    TreeNode* pre = NULL;   //           ，          pre 
};

Answer 2:非再帰法
考え方:
[問題を解く考え方]

         1
          \
           2
          / \
         3   4
              \
               5
                \
                 6

rootの左サブツリーを処理し、左サブツリーのルートノードと左サブツリーの右サブツリーを右サブツリーに挿入します.次にノード2を処理し,同様に2の左サブツリーを右サブツリーに挿入する.ノード2(ルートノードの左子)の最右ノード(左サブツリーの最上位層の最右ノード,最後にアクセス)にアクセスすることにより,左サブツリーの最後のノード(ノード4)を順に遍歴し,ルートノードに挿入された右サブ(ノード5)の前のノード(ノード4)を得た.この挿入プロセスを継続します.
Attention:
1.右の子の木の前のノードを見つけると、根のノードの左の子の最も右のノードになります.

TreeNode* ptr = root->left;
while(ptr->right) ptr = ptr->right;

2. 挿入方法に注意してください.結合図記憶

ptr->right = root->right;
root->right = root->left;
root->left = NULL;

3. rootをrootに設定した右の子供は、rootがNULLであることを知っています.つまり、rootがツリーの最後のノードに遍歴していることを知っています.
AC Code:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode *root) {
        while(root)
        {
            if(root->left)
            {
                TreeNode* ptr = root->left;
                while(ptr->right) ptr = ptr->right;
                ptr->right = root->right;
                root->right = root->left;
                root->left = NULL;
            }
            root = root->right;
        }
    }
};