给定一个二叉树,原地将它展开为一个单链表。

    例如,给定二叉树

    1. 1
    2. / \
    3. 2 5
    4. / \ \
    5. 3 4 6

    将其展开为:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    1
     \
      2
       \
        3
         \
          4
           \
            5
             \
              6
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    /*
     * @lc app=leetcode.cn id=114 lang=cpp
     *
     * [114] 二叉树展开为链表
     */
    
    // @lc code=start
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    public:
        void flatten(TreeNode* root) {
            if(root == nullptr)  return ;
    
            flatten(root->left);
            flatten(root->right);
    
            TreeNode* left, *right;
            left = root->left;
            right = root->right;
            root->right  = left;
            root->left = nullptr;
            TreeNode* p = root;
            while(p->right){
                p = p->right;
            }
            p->right = right;
    
        }
    };
    // @lc code=end