# 二叉树展开为链表

## 题目

1. 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。

2. 展开后的单链表应该与二叉树 先序遍历 顺序相同。

输入：root = [1,2,5,3,4,null,6]



输入：root = []



输入：root = [0]



1. 树中结点数在范围 [0, 2000] 内

2. -100 <= Node.val <= 100

## 思路

（1）通过前序遍历获取列表信息

（2）根据链表，重新构建 treeNode

## java 实现

public void flatten(TreeNode root) {
List<Integer> list = new ArrayList<>();
preorder(root, list);
if(root != null) {
// 清空左子树
root.left = null;
// 设置新的右子树
root.right = buildRightTree(list);
}
}

private TreeNode buildRightTree(List<Integer> list) {
TreeNode root = null;
TreeNode pre = null;
for(int i = list.size()-1; i > 0 ; i--) {
root = new TreeNode(list.get(i));
// 右子树
root.right = pre;
pre = root;
}
return root;
}

private void preorder(TreeNode treeNode, List<Integer> list) {
if(treeNode == null) {
return;
}
preorder(treeNode.left, list);
preorder(treeNode.right, list);
}


Runtime: 1 ms, faster than 33.44% of Java online submissions for Flatten Binary Tree to Linked List.
Memory Usage: 38.2 MB, less than 83.12% of Java online submissions for Flatten Binary Tree to Linked List.


# 优化思路

（1）如何实现一边遍历，一边设置对应的节点信息呢？

（2）如何才能不重复创建节点，而是直接更新已有的节点得到呢？

## 寻找前驱节点

### 算法流程

     1
/  \
2    5
/ \    \
3   4    6


【1】节点对应的左子树

   2
/ \
3   4


（1）将当前节点的右子节点赋给前驱节点的右子节点

     1
/
2
/ \
3   4
\
5
\
6


（2）然后将当前节点的左子节点赋给当前节点的右子节点

     1
/   \
2     2
/ \    / \
3   4   3  4
\      \
5      5
\      \
6      6


（3）并将当前节点的左子节点设为空

 1
\
2
/ \
3   4
\
5
\
6


## java 实现

public void flatten(TreeNode root) {
TreeNode curr = root;
while (curr != null) {
// 左子树不为空
if (curr.left != null) {
// 左子树
TreeNode next = curr.left;
// 前继结点
TreeNode predecessor = next;
while (predecessor.right != null) {
predecessor = predecessor.right;
}
predecessor.right = curr.right;
curr.left = null;
curr.right = next;
}
curr = curr.right;
}
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Flatten Binary Tree to Linked List.
Memory Usage: 38.3 MB, less than 83.12% of Java online submissions for Flatten Binary Tree to Linked List.