生活中可以没有诗歌，但不能没有诗意。
题目
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用
TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。-
展开后的单链表应该与二叉树 先序遍历 顺序相同。
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
解题思路
- 前序遍历：直接按前序遍历的顺序遍历树存储到队列中,然后依次相连。
- 递归：对于树的搜索优先考虑递归,展开左右子树后,相连。
前序遍历
class Solution {
public void flatten(TreeNode root) {
if(root == null) return;
List<TreeNode> list = new ArrayList<TreeNode>();
dfs(root, list);
int size = list.size();
TreeNode prev = list.get(0);
for (int i = 1; i < size; i++) {
prev.left = null;
prev.right = list.get(i);
prev = list.get(i);
}
}
public void dfs(TreeNode root, List<TreeNode> list) {
if (root != null) {
list.add(root);
dfs(root.left, list);
dfs(root.right, list);
}
}
}
复杂度分析
- 时间复杂度：
O(n)，n为树的节点数。 - 空间复杂度：
O(n)。
递归
class Solution {
public void flatten(TreeNode root) {
if (root == null) return;
flatten(root.left); // 先将左子树和右子树展开
flatten(root.right);
TreeNode left = root.left,right = root.right;
root.left = null; // 将左子树置空，将右子树接到左子树的位置上
root.right = left;
while (root.right != null) root = root.right; // 找到当前链表的末尾
root.right = right; // 将原来的右子树接在末尾
}
}
复杂度分析
- 时间复杂度：
O(n)，n为树的节点数。 - 空间复杂度：
O(1)。
