首页 > 其他分享 >剑指 Offer 07. 重建二叉树

剑指 Offer 07. 重建二叉树

时间:2022-08-14 20:33:45浏览次数:80  
标签:preorder TreeNode 07 Offer int inBegin 二叉树 inorder preBegin

1.题目:

输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

 

示例 1:

 

 

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]
 

限制:

0 <= 节点个数 <= 5000

 

2. 分析与代码:

重构二叉树看另一篇博客:重构二叉树 + 输出 (层序遍历、其他遍历) - 湘summer - 博客园 (cnblogs.com)

代码:

/**
 * 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:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return getBinaryTree(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
    }

    TreeNode* getBinaryTree(vector<int>& preorder,int preBegin,int preEnd,vector<int>& inorder,int inBegin,int inEnd){
        if(preBegin > preEnd)
            return NULL;
        TreeNode* tree = new TreeNode(preorder[preBegin]);
        // *tree = (preorder[preBegin],NULL,NULL);
        int r = findRootInInorder(inorder,inBegin,inEnd,preorder[preBegin]);
        int count = r-inBegin; //inBegin从0开始,无需加1
        if(r!=inBegin)
            tree->left = getBinaryTree(preorder,preBegin+1,preBegin+count,inorder,inBegin,r-1);
        if(r!=inEnd)
            tree->right = getBinaryTree(preorder,preBegin+count+1,preEnd,inorder,r+1,inEnd);
        return tree;
    }

    int findRootInInorder(vector<int>& inorder,int inBegin,int inEnd,int key){
        for(int i=inBegin;i<=inEnd;i++){
            if(inorder[i] == key)
                return i;
        }
        return 0;
    }
};

 

也可以用hashMap去查找根节点在中序遍历中的位置。

标签:preorder,TreeNode,07,Offer,int,inBegin,二叉树,inorder,preBegin
From: https://www.cnblogs.com/lxpblogs/p/16586244.html

相关文章

  • [AcWing 4507] 子数组异或和
    异或的性质点击查看代码#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;constintN=1e6+10;intn;inta[N];voidsolve(){......
  • Cannot find module ... or its corresponding type declarations.(ts2307)
    https://blog.csdn.net/lx1996082566/article/details/121595946?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2~default~CTRLIST~Ra......
  • 1070 结绳——25分
    给定一段一段的绳子,你需要把它们串成一条绳。每次串连的时候,是把两段绳子对折,再如下图所示套接在一起。这样得到的绳子又被当成是另一段绳子,可以再次对折去跟另一段绳子串......
  • hdu7207-Find different【burnside引理】
    正题题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=7207题目大意一个序列\(a\),和它相同的序列当且仅当能通过以下操作实现相同:将\(a_1\)丢到\(a_n\),其余的向......
  • Acwing 第 64 场周赛 C 4507. 子数组异或和(异或+前缀和)
    https://www.acwing.com/problem/content/4510/给定一个长度为n的整数数组a1,a2,…,an。请你统计一共有多少个数组a的非空连续子数组能够同时满足以下所有条件:该......
  • 2022-8-14 剑指offer-二叉树递归
    剑指OfferII049.从根节点到叶节点的路径数字之和难度中等34收藏分享切换为英文接收动态反馈给定一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 ......
  • 从二叉树根节点搜索到指定结点的路径
    LC236题,二叉树的最近公共祖先:https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/其中一种解法的关键,是找到从根节点到指定结点的路径。 pu......