大家好！我是曾续缘❤️
今天是《LeetCode 热题 100》系列
发车第 46 天
二叉树第 11 题
❤️点赞 👍 收藏 ⭐再看，养成习惯

给你二叉树的根结点 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]
提示：
树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100

进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
难度：💖💖

解题方法

这道题目要求将给定的二叉树展开为一个单链表，同时要求展开后的单链表与二叉树的先序遍历顺序相同。

我们可以使用迭代的方法来实现展开操作。

对于每个节点，首先将其左子树连接到根节点，然后将右子树接到左子树的最右节点。虽然连接左子树的第一个节点很容易，但连接右子树后，就无法直接访问右子树的节点。为了解决这个问题，在连接左子树之前，我们应该先将右子树连接到左子树上。根据前序遍历的性质，左子树的最右节点也是左子树最后连接的节点，同时也是叶子节点。我们将右子树连接到这个节点上，然后按照要求进行连接。

具体步骤如下：

初始化指针cur为根节点root。
循环遍历二叉树的每个结点，直到cur为空。
在每次循环中，判断当前结点cur是否有左子树。
- 如果有左子树，则找到左子树的最右结点p，将当前结点cur的右子树连接到p的右指针上，并将当前结点的左子树置为空。
- 如果没有左子树，则直接将指针cur移动到下一个结点。
最后，整个二叉树就被展开成了一个单链表。

Code

查看代码

java

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        TreeNode cur = root;
        while(cur != null){
            if(cur.left != null){
                TreeNode next = cur.left;
                TreeNode p = next;
                while(p.right != null){
                    p = p.right;
                }
                p.right = cur.right;
                cur.left = null;
                cur.right = next;
            }
            cur = cur.right;
        }
    }
}

解题方法 ​

Code ​

解题方法

Code