114. 二叉树展开为链表
程序员文章站
2024-03-26 13:38:11
...
题目：
题解：
解题思路：
思路来源于很多人的题解，按先序遍历来看，1的右子树5,6都该在4的后面。
1
/ \
2 5
/ \ \
3 4 6 ,
所以我们可以直接将1节点的右子树（5 -> 6）移接到左子树的最右边节点4上：
1
/
2
/ \
3 4
\
5
\
6,然后把整个左子树（2，3，4，5，6）移到右边，这样我们就完成了第一层的恢复：
1
\
2
/ \
3 4
\
5
\
6 然后进入右子树，继续上面的操作：
1
\
2
/
3
\
4
\
5
\
6 我们可以直接将2节点的右子树（4 -> 5 -> 6）移接到左子树的最右边节点3上：
1
\
2
\
3
\
4
\
5
\
6 然后把整个左子树（3，4，5，6）移到右边，这样我们就完成了第二层的恢复：
结束。
代码：
1. 递归法：
/**
* code114
*/
public class code114 {
public static void flatten(TreeNode root) {
if (root == null) {
return;
}
if (root.left != null) {
TreeNode pre = root.left;
while (pre.right != null) {
pre = pre.right;
}
pre.right = root.right;
root.right = root.left;
root.left = null;
}
flatten(root.right);
}
public static void main(String[] args) {
Integer nums[] = { 1, 2, 5, 3, 4, null, 6 };
TreeNode tree = ConstructTree.constructTree(nums);
System.out.println("***************************************");
TreeOperation.show(tree);
System.out.println("***************************************");
flatten(tree);
TreeOperation.show(tree);
System.out.println("***************************************");
}
}
2. 迭代法：
/**
* code114
*/
public class code114 {
// 迭代法：
public static void flatten(TreeNode root) {
if (root == null) {
return;
}
while (root != null) {
if (root.left != null) {
TreeNode pre = root.left;
while (pre.right != null) {
pre = pre.right;
}
pre.right = root.right;
root.right = root.left;
root.left = null;
}
root = root.right;
}
}
public static void main(String[] args) {
Integer nums[] = { 1, 2, 5, 3, 4, null, 6 };
TreeNode tree = ConstructTree.constructTree(nums);
System.out.println("***************************************");
TreeOperation.show(tree);
System.out.println("***************************************");
flatten(tree);
TreeOperation.show(tree);
System.out.println("***************************************");
}
}