二叉树展开为单链表

[编程题]二叉树展开为单链表

热度指数：1013 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个节点个数为n的二叉树，请你把这个二叉树展开为一条单链表。

1.展开后的链表同样是TreeNode，其中right指针指向下一个节点，left节点为空

2.链表的顺序与给定二叉树的先序遍历顺序相同。

3.该题不需要返回链表或者树，请你在原树上面操作，系统会最后检查原树的情况来判断你的代码是否正确

4.该题有O(1)额外空间复杂度的解法，你能实现吗？传入的TreeNode不计入空间复杂度计算

例如：

原二叉树是

展开后是

数据范围：二叉树的节点数满足 $0 \le n \le 10^5 \$ ，二叉树节点值满足 $1 \le val \le 10^5 \$

示例1

输入

{1,2,3,4,8}

输出

{1,#,2,#,4,#,8,#,3}

示例2

输入

{0}

输出

{0}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Acmen_沉梦昂志

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     */
    TreeNode* last = NULL;  // 从后往前 插入
    void expandTree(TreeNode* root) {
        // write code here
        if(!root) return ;
        expandTree(root->right);
        expandTree(root->left);
        //if(pre == NULL) pre = root;
        root->right = last;
        root->left = NULL;
        last = root;
    }
};

从后往前插

发表于 2022-03-01 21:05:58 回复(0)

fatzard

时间复杂度o（n）空间复杂度o（1）

递归式写法：其实子问题就是把左子树变为右子树，然后把最开始的右子树接在新的右子树下面，然后就一直递归下去，递归终止到左子树为一个节点为止，那么再进行回溯，最终这颗树就变成了一个单链。注意的是需要用一个指针rear来记录左子树的最后一个节点。

struct TreeNode* build(struct TreeNode* root,struct TreeNode** rear)
{
    if(!root)return root;
    struct TreeNode* rchild=root->right;
    struct TreeNode* head=root;
    if(root->left)
    {
        root->right=build(root->left,rear);
        root->left=NULL;
        root=*rear;
        root->right=rchild;
    }
    if(root->right)
    {
        root->right=build(root->right,rear);
    }
    else *rear=root;
    return head;
}
struct TreeNode* expandTree(struct TreeNode* root ) {
    if(root==NULL)return root;
    return build(root,&root);
}

发表于 2023-10-09 18:54:14 回复(0)

小谷围做题家

package main
//import "fmt"
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
*/
func expandTree( root *TreeNode )  {
    arr:=[]*TreeNode{}
    var order func(*TreeNode)
    order=func(root *TreeNode){
        if root==nil{
            return
        }
        arr=append(arr,root)
        order(root.Left)
        order(root.Right)
    }
    order(root)
    for i,p:=range arr{
        p.Left=nil
        if i<len(arr)-1{
            p.Right=arr[i+1]
        }else{
            p.Right=nil
        }
    }
}

发表于 2023-03-15 11:17:33 回复(0)