LeetCode_Flatten Binary Tree to Linked List

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

テーマの要求に従って、実際には2つのフォークの木を右の息子のポインタでリンクされたチェーンテーブルに変換し、私自身の解法は再帰です.
すなわち、ノードrについては、まずrの左サブツリーの構造改造を実現し、次に右サブツリーに置き換え、右サブツリーチェーンを最も右側のノードにおいて、コードは以下の通りである.

  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };
 
class Solution {
public:
    /*void flatten(TreeNode *root) {
       root=FlattenTree(root); 
    }
    TreeNode *FlattenTree(TreeNode *root){
        if(root==NULL){
            return NULL;
        }
        TreeNode *right=root->right;
        root->right=FlattenTree(root->left);
        root->left=NULL;
        TreeNode *temp=root;
        while (temp->right!=NULL){
            temp=temp->right;
        }
        temp->right=FlattenTree(right);
        return root;
    }*/
    void flatten(TreeNode* root) {

        if (!root) return;

        TreeNode* node = root;
        while (node) {

            // Attatches the right sub-tree to the rightmost leaf of the left sub-tree:
            if (node->left) {

                TreeNode *rightMost = node->left;
                while (rightMost->right) {

                    rightMost = rightMost->right;
                }
                rightMost->right = node->right;

                // Makes the left sub-tree to the right sub-tree:
                node->right = node->left;
                node->left = nullptr;
            }

            // Flatten the rest of the tree:
            node = node->right;
        }    
    }
};

注釈部分は私自身が提出したコードであり、ACも使用されているが、再帰を使用するとアルゴリズムの時空複雑度が最適ではなく、その後使用されたコードはDiscussで他の人のものであり、巧みに再帰を反復に変換している.