leetcode114.二叉树转换为链表

    1
   /   2   5
 / \   3   4   6

//将 1 的左子树插入到右子树的地方
    1
           2         5
     / \             3   4         6        
//将原来的右子树接到左子树的最右边节点
    1
           2          
     / \          
    3   4  
                   5
                       6
            
 //将 2 的左子树插入到右子树的地方
    1
           2          
       \          
        3       4  
                                   5
                                       6   
        
 //将原来的右子树接到左子树的最右边节点
    1
           2          
       \          
        3      
                   4  
                       5
                           6         

void flatten(TreeNode* root)
{
    if(!root) return;
    while(root) {
        if(!root->left) {
            root = root->right;
        }
        else {
            //找左子树最右边节点
            TreeNode* pre = root->left;
            while(pre->right) {
                pre = pre->right;
            }
            //将原来的右子树接到左子树最右边
            pre->right = root->right;
            root->right = root->left;
            root->left = NULL;
            //考虑下一个节点
            root = root->right;
        }
    }
}