剑指offer刷题笔记——重建二叉树

2021年11月25日 阅读数:2
这篇文章主要向大家介绍剑指offer刷题笔记——重建二叉树,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

题目描述

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。ide

思路

  • 涉及二叉树的问题,应该条件反射般的使用递归(无优化要求时)
  • 前序遍历的第一个值为根节点的值,使用这个值将中序遍历结果分红两部分,左部分为左子树的中序遍历结果,右部分为右子树的中序遍历的结果。
  • 示例
前序
  1,2,4,7,3,5,6,8
中序
  4,7,2,1,5,3,8,6

第一层
  根节点 1
  根据根节点的值(不重复),划分中序:
    {4,7,2} 和 {5,3,8,6}
  根据左右子树的长度,划分前序:
    {2,4,7} 和 {3,5,6,8}
  从而获得左右子树的前序和中序
    左子树的前序和中序:{2,4,7}、{4,7,2}
    右子树的前序和中序:{3,5,6,8}、{5,3,8,6}

第二层
  左子树的根节点 2
  右子树的根节点 3
  ...

code

class Solution{
public:
    TreeNode *reConstructBinaryTree(vector<int> pre,vector<int> vin){
        return reConstructCore(pre,0,pre.size(),vin,0,vin.size());
    }
    TreeNode *reConstructCore(vector<int> &pre,int pre_beg,int pre_end,vector<int> &vin,int vin_beg,int vin_end){
        if(pre_end-pre_beg<=0)
            return NULL;
        TreeNode* root=new TreeNode{ pre[pre_beg] };
        for(auto i=0;i<vin_end-vin_beg;i++){
            if(vin[i+vin_beg]==pre[pre_beg]){
                root->left=reConstructCore(pre,pre_beg+1,pre_beg+1+i,vin,vin_beg,vin_beg+i);
                root->right=reConstructCore(pre,pre_beg+1+i,pre_end,vin,vin_beg+1+i,vin_end);
            }
        }
        return root;
    }
};