问题描述
LeetCode 114. 二叉树展开为链表 (opens in a new tab)，难度中等。
给你二叉树的根结点 root ，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用
TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。 - 展开后的单链表应该与二叉树 先序遍历 (opens in a new tab) 顺序相同。
示例 1
输入：root = [1,2,5,3,4,null,6] 输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2
输入：root = [] 输出：[]
示例 3
输入：root = [0] 输出：[0]
提示：
- 树中结点数在范围
[0, 2000]内 -100 <= Node.val <= 100
进阶： 你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
题解
DFS
解题思路：先用 DFS 遍历二叉树，将树的结果存放在 List 中，然后更新原先的二叉树。
Solution.java
class Solution {
public void preorderTraversal(List<TreeNode> traList, TreeNode root) {
if (root == null) {
return;
}
traList.add(root);
preorderTraversal(traList, root.left);
preorderTraversal(traList, root.right);
}
public void flatten(TreeNode root) {
List<TreeNode> traList = new ArrayList<>();
preorderTraversal(traList, root);
TreeNode temp = root;
for (int i = 1; i < traList.size(); ++i) {
temp.right = traList.get(i);
temp.left = null;
temp = temp.right;
}
}
}