LeetCode/114. 二叉树展开为链表

114. 二叉树展开为链表

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

例如，给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6

将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

题解：

本题分享一种最直观的思路，我们通过观察，可以发现该链表的顺序就是前序遍历，直接先进行前序遍历，然后原地组成链表即可。

具体代码如下：

import java.util.LinkedList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<TreeNode> result = new LinkedList<>();

    public void flatten(TreeNode root) {
        preOrder(root);

        for (int i = 1; i < result.size(); i++) {
            TreeNode pre = result.get(i - 1);
            TreeNode curr = result.get(i);
            pre.left = null;
            pre.right = curr;
        }
    }

    void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        result.add(root);
        preOrder(root.left);
        preOrder(root.right);
    }
}

还有一种方法可以大幅度提高时间复杂度，但是不太好想，要用到递归的思想。我们思考每一个结点都需要做什么，基本上就是先将root的左右结点保存起来，然后将root.left赋值给root.right，并将root.left置为空，最后将原先保存的root.right接到新形成的树的后面即可。不需要考虑如何递归，只需要把每一个结点需要干什么想清楚就行。我们只需要对每个结点做上述操作，自然而然的进行递归后，左右子树就会被拉成链表。

具体代码如下：

import java.util.LinkedList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
		  //将左右子树拉平成链表
        flatten(root.left);
        flatten(root.right);

        //将根结点的左右子树保存
        TreeNode left = root.left;
        TreeNode right = root.right;

        //左子树置空，原先的左子树接到root的右子树上
        root.left = null;
        root.right = left;

        //将原来右子树续到新子树后面
        TreeNode p = root;
        while (p.right != null) {
            p = p.right;
        }
        p.right = right;
    }

}