关于#二叉树展开为链表#的问题，如何解决？

Question

关于leetcode将二叉树展开为链表的一道题目，感觉代码逻辑思维没啥错，然后调试了一下，感觉应该是全部正确输出，但是实际上却是会少掉3,4，就很疑惑，为什么会造成这样的结果，val值为2的这个节点，应该在递归回溯的时候把val值为3的这个节点给连接上了的诶，不知道我是哪里想错了。

```java
public void flatten(TreeNode root) {
        flatten1(root);
    }
    public TreeNode flatten1(TreeNode root){
        if(root==null)
            return null;
        if(root.left==null||root.right==null)
            return root;
        TreeNode temp=root.right;
        root.right=null;
        root.right=flatten1(root.left);
        //注意这里要将左子树置为null
        root.left=null;
        root.right.right=temp;
        return root;
    }

```

Answer 1

【以下回答由 GPT 生成】

public void flatten(TreeNode root) {
    flatten1(root);
}

public TreeNode flatten1(TreeNode root){
    // 终止条件：当前节点为空
    if(root == null)
        return null;
    // 左右子树已经被拉平成链表
    TreeNode left = flatten1(root.left);
    TreeNode right = flatten1(root.right);

    // 后序遍历位置

    // 1. 将左子树作为右子树
    root.left = null;
    root.right = left;

    // 2. 将原先的右子树接到当前右子树的末端
    TreeNode cur = root;
    while(cur.right != null){
        cur = cur.right;
    }
    cur.right = right;

    return root;
}

首先，我们需要明确一下题目要求，需要将给定的二叉树原地展开为链表，展开后的链表需要满足如下要求： 1. 原先的右子树被连接为当前节点的右子树。 2. 原先的左子树被移到右子树的位置上。 3. 原先的左子树的右子树被移到左子树的位置上，原先的右子树被连接到当前右子树末尾。

根据题目要求，我们可以使用递归实现解题。具体步骤如下：

1. 判断当前节点是否为空，若为空则直接返回。
2. 递归处理当前节点的左子树，得到左子树拉平后的链表。
3. 递归处理当前节点的右子树，得到右子树拉平后的链表。
4. 将当前节点的左子树和右子树断开，将左子树作为当前节点的右子树。
5. 找到当前右子树的末尾节点，将原先的右子树连接到末尾节点的右侧。

在代码实现中，我们使用了一个辅助函数 flatten1 来处理递归过程。在这个辅助函数中，我们首先判断当前节点是否为空，若为空则直接返回。然后，我们递归调用 flatten1 函数来处理当前节点的左子树和右子树。接着，我们将当前节点的左子树作为右子树，并将原先的右子树连接到右子树的末尾。

最后，我们将调用 flatten1(root) 函数来开始递归处理并返回结果。

这样，我们就能够正确地将二叉树展开为链表了。

【相关推荐】

• 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/7760711
• 我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：2020-11-16：手写代码：leetcode第406题。假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。
• 除此之外, 这篇博客: 【LeetCode滑动窗口】最大连续1的个数&替换后的最长重复字符&尽可能使字符串相等&k个不同整数的子数组中的 替换后的最长重复字符 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^