LeetCode刷题实战114：二叉树展开为链表-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 二叉树展开为链表，我们先来看题面：

https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/

Given a binary tree, flatten it to a linked list in-place.

题意

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

样例

解题

https://www.cnblogs.com/gongyanzh/p/12901595.html

将左子树插入到右子树的地方

将原来的右子树接到左子树的最右边节点

考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null

     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

思路看上面，代码实现：

class Solution {
    public void flatten(TreeNode root) {
        //将左子树接到右子树 root.right = root.left
        //为了做到这一点，首先要把右子树移走，移到哪？移到左子树的右子树
        //pre = root.left; pre.right = root.right;
        while(root != null){
            //左子树为空，直接考虑下个节点
            if(root.left == null){
                root = root.right;
            }else{
                TreeNode pre = root.left;
                while(pre.right != null){
                    pre = pre.right;
                }
                pre.right = root.right;
                root.right = root.left;
                root.left = null;
                root = root.right;
            }
        }
    }
}