LeetCode-114-二叉树展开为链表
二叉树展开为链表
【LeetCode-114-二叉树展开为链表】题目描述:给你二叉树的根结点 root ,请你将它展开为一个单链表:解法一:递归
示例说明请见LeetCode官网。
- 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。
- 展开后的单链表应该与二叉树 先序遍历 顺序相同。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
使用递归的方式求解,递归过程如下:
- 如果当前根节点为null时,直接返回;
- 如果当前根节点的左右子节点都为空时,不需要调整,直接返回;
- 如果当前根节点的左子树为空,则只需要递归处理当前根节点的右子树;
- 如果当前根节点的右子树为空时,则需要递归处理当前根节点的左子树,然后将当前根节点的左子节点指向null,右子节点指向处理后的左子树;
- 如果当前根节点的左右子树都不为空,则分别递归处理当前根节点的左右子树,然后将根节点的左子节点指向null,右子节点指向处理后的左子树,然后将左子树的最后一个节点指向处理后的右子树。
import com.kaesar.leetcode.TreeNode;
public class LeetCode_114 {
/**
* 递归
*
* @param root
*/
public static void flatten(TreeNode root) {
// 当前根节点为null时,直接返回
if (root == null) {
return;
}
// 当前根节点的左右子节点都为空时,不需要调整,直接返回
if (root.left == null && root.right == null) {
return;
}
if (root.left == null) {
// 当前根节点的左子树为空,则只需要递归处理当前根节点的右子树
flatten(root.right);
return;
}
if (root.right == null) {
// 当前根节点的右子树为空时,则需要递归处理当前根节点的左子树,然后将当前根节点的左子节点指向null,右子节点指向处理后的左子树
TreeNode left = root.left;
flatten(left);
root.right = left;
root.left = null;
return;
}
// 如果当前根节点的左右子树都不为空
TreeNode left = root.left;
// 递归处理左子树,并找到处理后的最后一个节点
flatten(left);
TreeNode leftLast = left;
while (leftLast.right != null) {
leftLast = leftLast.right;
}
TreeNode right = root.right;
// 递归处理右子树
flatten(right);
// 最后将根节点的左子节点指向null,右子节点指向处理后的左子树,然后将左子树的最后一个节点指向处理后的右子树
root.right = left;
leftLast.right = right;
root.left = null;
}public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(5);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(4);
root.right.right = new TreeNode(6);
System.out.println("展开为链表之前");
root.print();
System.out.println("展开为链表之后");
flatten(root);
root.print();
}
}
【每日寄语】 我们的人生像云霄飞车,充满高低与刺激,我们经历多,心理建设要强壮,眼界开,胸怀要放大。
推荐阅读
- 【生信技能树】R语言练习题|【生信技能树】R语言练习题 - 中级
- java中如何实现重建二叉树
- 种树郭橐驼传(文言句式+古今异义+词类活用+通假字)
- 白杨树
- 08黑龙江迟淑荣弯柳树网络学院第五期学习赵宗瑞老师主讲的(传统文化与身心健康)教育体系心得体会
- [原创]能见沂山一棵树,胜读十年无用书!
- 涵养字外功
- 2018.07.07《刺杀骑士团长》村上春树
- 二叉树路径节点关键值和等于目标值(LeetCode--112&LeetCode--113)
- 撒哈拉沙漠-三毛