LeetCode 练习——114. 二叉树展开为链表
文章目录
- 1.题目描述
- 2.思路
-
- 2.1 代码
- 2.2 测试结果
- 3.总结
1.题目描述
二叉树展开为链表
给你二叉树的根结点 root ,请你将它展开为一个单链表:
展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例 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]
2.思路
2.1 代码
题目要求链表顺序与先序遍历结果相同,因此整体使用二叉树先序遍历。因为需要让节点的左节点为 null、右节点为先序遍历时下一次经过的节点,因此使用一个 pre 变量来保存遍历经过的上一个节点。同时,因为需要构造 pre 节点的左右子节点,所有将当前节点的左右两个节点事先提取出来。代码如下:
class Solution { private TreeNode pre; public void flatten(TreeNode root) { if (root == null) { return; } process(root); } public void process(TreeNode root) { if (root == null) { return; } if (pre != null) { pre.right = root; pre.left = null; } TreeNode left = root.left; TreeNode right = root.right; pre = root; process(left); process(right); }}
2.2 测试结果
通过测试
3.总结
- 整体结构使用二叉树先序遍历
- 使用 pre 变量来保存上一次经过的节点
- 使用 left 和 right 两个变量来保存当前节点的左右子节点,同时通过当前节点构造pre节点的左右子树