leetcode114. 二叉树展开为链表

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

例如，给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6
将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

思路：所有左子树的最右节点接上右子树即可。

比如例子中：3接上4，4接上5

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * Definition for a binary tree node.
     
    
   

    

     

    
    

     

       * public class TreeNode {
     
    
   

    

     

    
    

     

       * int val;
     
    
   

    

     

    
    

     

       * TreeNode left;
     
    
   

    

     

    
    

     

       * TreeNode right;
     
    
   

    

     

    
    

     

       * TreeNode(int x) { val = x; }
     
    
   

    

     

    
    

     

       * }
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     
 public void flatten(TreeNode root) {
     
    
   

    

     

    
    

     
 while (root != null) {
     
    
   

    

     

    
    

     
 if (root.left != null) {
     
    
   

    

     

    
    

     
 // 找左子树最右边的节点
     
    
   

    

     

    
    

     

       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;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/104127313