一、题目
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
二、示例
2.1> 示例 1：
【输入】root = [1,2,5,3,4,null,6]
【输出】[1,null,2,null,3,null,4,null,5,null,6]
2.2> 示例 2：
【输入】root = []
【输出】[]
2.3> 示例 3：
【输入】root = [0]
【输出】[0]
提示：
- 树中结点数在范围
[0, 2000]内 -
-100<= Node.val <=100
进阶：
- 你可以使用原地算法（
O(1)额外空间）展开这棵树吗？
三、解题思路
根据题目描述，需要我们根据给定的二叉树，然后对其进行先序遍历/前序遍历，从而拼装出一条链表。那么，首先我们先要弄清楚二叉树的遍历方式，我们以三个节点为例：node、leftNode和rightNode。遍历方式如下所示：
【前序遍历】
node——>leftNode——>rightNode
【中序遍历】leftNode——>node——>rightNode
【后序遍历】leftNode——>rightNode——>node
那么，了解了先序遍历方式之后，就可以通过遍历一次二查树，将树节点TreeNode保存到List中，然后再针对List进行遍历操作，从而构造一条先序顺序的链表。
但是，我们从题目描述的“进阶”部分可以看到它的要求，即：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？ 那么我们就不能使用List来进行TreeNode的存储了。我们此时就需要每当遍历一个树节点就进行一次链表拼装操作。那怎么操作呢?
【首先】创建两个指针，分别为遍历用的指针
node，和指针node的前置指针preNode；
【其次】当preNode没有被初始化时，则preNode就指向node；
【第三】每当指针node遍历的下一个节点时，都是将preNode节点的right指向node节点，将preNode节点的left指向null；
【第四】preNode指针移动到node指针处，然后再重复第三步骤，直至整棵树遍历完毕；
上面就是本题的解题思路，为了方便理解，下面我们以root = [1,2,5,3,4,null,6]为例，看一下具体的处理过程是怎么样的。请见下图所示：
四、代码实现
class Solution {
TreeNode preNode;
public void flatten(TreeNode root) {
if (root == null) return;
TreeNode leftNode = root.left;
TreeNode rightNode = root.right;
if (preNode == null) preNode = root;
else {
preNode.right = root;
preNode.left = null;
preNode = root;
}
flatten(leftNode);
flatten(rightNode);
}
}
/**
* Definition for a binary tree node.
* public 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;
* }
* }
*/
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
网友评论