二叉树展开为链表
题目介绍
给你二叉树的根结点 root ，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用
TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
- 展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例 1：
1
2
| 输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
|
示例 2：
示例 3：
提示：
- 树中结点数在范围
[0, 2000] 内
-100 <= Node.val <= 100
题目解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| package algorithm;
import java.util.LinkedList;
import java.util.Queue;
public class FlattenBinaryTreeToLinkedList {
static Queue<TreeNode> queue = new LinkedList<>();
public static void flatten(TreeNode root) {
queue.clear();
dfs(root);
TreeNode lamb = new TreeNode();
while (queue.size() >= 1) {
TreeNode node = queue.poll();
node.left = null;
node.right = null;
lamb.right = node;
lamb = lamb.right;
}
System.out.println();
}
private static void dfs(TreeNode root) {
if (root == null) {
return;
}
queue.offer(root);
dfs(root.left);
dfs(root.right);
}
public static void main(String[] args) {
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
n1.left = n2;
TreeNode n3 = new TreeNode(5);
n1.right = n3;
TreeNode n4 = new TreeNode(3);
n2.left = n4;
TreeNode n5 = new TreeNode(4);
n2.right = n5;
TreeNode n6 = new TreeNode(6);
n3.right = n6;
flatten(n1);
}
public static 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;
}
}
}
|
打印：
思路：
思路上，很简单。效率当然也是一般。后续有时间可以优化一下思路。