1. 云栖社区>
  2. >
  3. 正文

二叉树专题-根据前序和中序序列构造二叉树

作者:用户 来源:互联网 时间:2018-09-11 18:59:28

数据结构二叉树leetcodeLintCodelintcode题解

二叉树专题-根据前序和中序序列构造二叉树 - 摘要: 本文讲的是二叉树专题-根据前序和中序序列构造二叉树, 经典的二叉树构造的问题,例子:(注意题目中限定了,没有重复的元素),先序为2143,中序为1423 我们先手算一下,看看是如何构造的。先序第一个为2,则根为2,那么去中序中找2,就能够区分左右子树了。14在左子树,3

经典的二叉树构造的问题,例子:(注意题目中限定了,没有重复的元素),先序为2143,中序为1423

我们先手算一下,看看是如何构造的。先序第一个为2,则根为2,那么去中序中找2,就能够区分左右子树了。14在左子树,3在右子树。且左子树的先序序列为14,中序也为14.....可以分析出来这是一个递归的过程。手工算到最后,很容易构造出二叉树。

二叉树专题-根据前序和中序序列构造二叉树

故递归函数必须要有preL,preR,inL,inR这些参数,作为当前的先序中序序列的左右区间。先根据先序第一个值找到根,再去中序中找相等的值(假设下标为k),区分左右子树即可,关键是要计算正确左右子树的范围。左子树的节点数numLeft=k-inL

一般性的过程如下,inL,inR,preL,preR均为数组下标

二叉树专题-根据前序和中序序列构造二叉树

推到这里了,很容易写出代码:

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
 

class Solution {
    /**
     *@param preorder : A list of integers that preorder traversal of a tree
     *@param inorder : A list of integers that inorder traversal of a tree
     *@return : Root of a tree
     */
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        // write your code here
        if(preorder.empty()||inorder.empty())
        return NULL;
        return build(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
    }
    TreeNode* build(vector<int> preorder,vector<int> inorder,int preL,int preR,int inL,int inR){
        if(preL>preR)//终止条件
        return NULL;
        int rootValue=preorder[preL];//先序第一个值即为根的值
        TreeNode* root=new TreeNode(rootValue);
        //寻找左右子树的划分
        int k;
        for(int i=0;i<inorder.size();++i){
            if(rootValue==inorder[i]){
                k=i;
                break;
            }
        }
        int numLeft=k-inL;
        root->left=build(preorder,inorder,preL+1,preL+numLeft,inL,k-1);
        root->right=build(preorder,inorder,preL+numLeft+1,preR,k+1,inR);
        return root;
    }
};


以上是云栖社区小编为您精心准备的的内容,在云栖社区的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索数据结构 , 二叉树 , leetcode , LintCode lintcode题解 ,以便于您获取更多的相关知识。

弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率

40+云计算产品,6个月免费体验

现在注册,免费体验40+云产品,及域名优惠!

云服务器9.9元/月,大学必备