请选择 进入手机版 | 继续访问电脑版

石家庄老站长

点击联系客服
客服QQ:509006671 客服微信:mengfeiseo
 找回密码
 立即注册
查看: 8|回复: 0

《剑指offer刷题笔记》 6 二进制树重建[c详细问题解决]

[复制链接]

1

主题

1

帖子

-7

积分

限制会员

积分
-7
发表于 7 天前 | 显示全部楼层 |阅读模式
题目

要输入二叉树之前和中间顺序遍历的结果,请重建二叉树。

注意:

二叉树中每个节点的值是不同的。输入前顺序巡回和中间顺序巡回是合法的。样例

给定:

以前的顺序巡回是[3,9,20,15,7]

中间顺序遍历示例:[9,3,15,20,7]

返回:[3,9,20,null,null,15,7,null,null,null,null,null]

返回的二叉树如下:

3

/\

9 20

/\

15 7

思路

(递归)

o

(请参阅。)

n

)。

O(n)。

O(n)。

递归地设置整个二叉树。首先递归创建左右子树,然后创建根节点,让指针指向两个子树。

具体步骤如下:

首先,使用前面的顺序查找根节点。前一个顺序中的第一个数字是根节点的值。如果在中间顺序遍历中找到根节点的位置K,则K左侧是左侧子树的中间顺序遍历,右侧是右侧子树的中间顺序遍历。假设左侧子树的中间顺序遍历的长度为L,则在上一顺序遍历中,根节点后面的L数是左侧子树的上一顺序遍历,其余数是右侧子树的上一顺序遍历。通过左右子树的上一个和中间顺序遍历,可以在创建根节点之前递归地创建左右子树。时间复杂度分析

初始化时,使用哈希表(unordered_mapint,int)在中间顺序遍历中记录每个值的位置,因此,递归到每个节点时,在中间顺序遍历中查找根节点位置的任务是

o

(请参阅。)

1
      
        )
      
      
      
       O(1)
      
     
    O(1)的时间。此时,创建每个节点需要的时间是
   
     
      
      
        O
      
      
        (
      
      
        1
      
      
        )
      
      
      
       O(1)
      
     
    O(1),所以总时间复杂度是
   
     
      
      
        O
      
      
        (
      
      
        n
      
      
        )
      
      
      
       O(n)
      
     
    O(n)。

代码
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
    unordered_mapint,int> pos;
    TreeNode* buildTree(vectorint>& preorder, vectorint>& inorder) {
        int n = preorder.size();
        for (int i = 0; i  n; i ++ )
            pos[inorder] = i; //将根节点的位置记录下来
        return dfs(preorder, inorder, 0, n - 1, 0, n - 1);//递归创建左右子树,最后将根节点指向左右子树
    }
    TreeNode* dfs(vectorint>&pre, vectorint>&in, int pl, int pr, int il, int ir)
    {
        if (pl > pr) return NULL; //如果左区间大于右区间,直接返NULL
        int k = pos[pre[pl]] - il; //前序遍历区间的长度
        TreeNode* root = new TreeNode(pre[pl]);//创建根节点
        root->left = dfs(pre, in, pl + 1, pl + k, il, il + k - 1); //左子树的前序和中序遍历区间
        root->right = dfs(pre, in, pl + k + 1, pr, il + k + 1, ir);//右子树的前序和中序遍历区间
        return root;
    }
};
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|无图版|手机版|小黑屋|石家庄@IT精英团

GMT+8, 2021-4-13 18:49 , Processed in 0.079349 second(s), 25 queries .

Powered by Discuz! X3.4

© 2001-2021 Comsenz Inc.

快速回复 返回顶部 返回列表