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