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

石家庄老站长

点击联系客服
客服QQ: 客服微信:
 找回密码
 立即注册
查看: 13|回复: 1

LeetCode二叉树重建详细信息

[复制链接]

1

主题

1

帖子

-7

积分

限制会员

积分
-7
发表于 2021-9-13 07:20:04 | 显示全部楼层 |阅读模式
LeetCode重建二叉树详解

标题说明原理分析(1)大致思考(2)详细说明代码的实现(1)主函数(2)确定递归函数参数间隔递归结束条件综述

题目描述





原理分析

(1)大致思路

下面介绍了上一顺序遍历中顺序遍历如何确定唯一的二叉树。有关二叉树的基本内容,请参阅二叉树的基本操作和联系方式。对此,不再重复过度。对于以前的顺序遍历顺序:根、左子树、右子树;中间顺序的遍历顺序:左侧子树、根、右侧子树。因此,通过上一个顺序遍历,上一个顺序中的第一个节点是这个树的根,在中间顺序遍历中可以找到该节点的位置。(阿尔伯特爱因斯坦,Northern  Exposure(美国电视连续剧),成功)在中间顺序中,根的左侧全部是属于根左侧子树的节点,根的右侧全部是属于根的右侧子树的节点。详细如图:





完成第一阶段后,我们将具体掌握当前哪个是根节点,哪个节点分别属于左右子树。但是因为树的递归特性。属于左侧子树的节点仍然符合以前的顺序遍历、中间顺序遍历特征。因此,对于刚刚分离的两个部分,必须再次使用上述方法来确定根节点,并确定属于左侧子树的节点和属于右侧子树的节点。类推一次,直到结束。这就是这个问题的大体想法。

(2)细节阐述

这个问题还有不少值得思考的地方。

1、我们如何表示哪些节点属于左边的子树,右边的子树?

A:以前的顺序,中间的顺序都是vector,所以用下标确定范围就可以了。之前的顺序:[根,左侧子树,右侧子树]。中间顺序:[左边的子树,根,右边的子树]。它们都集中了三种节点,很容易区分。

2、递归终止条件是什么?

答:这需要结合具体的代码分析,现在我们控制范围的时候,如果范围是非法的(不存在的话),就可以确认。
09;的情况就说明已经没有左子树或者右子树了,就要返回。


代码实现
注:一般在我的题解中,范围控制,代码这样书写的原因都会通过注释的方式写在对应代码旁边,帮助读者理解分析代码,这样更有针对性。因此,如果读者对于前面的题目分析有疑惑或者不理解的地方,请仔细阅读代码及旁边注释,一定会对你有所启发,帮助你的理解!!

(1)主函数
TreeNode* buildTree(vectorint>& preorder, vectorint>& inorder) {
        //_buildTree本题因为需要递归实现,因此需要借助一个递归函数。
       return _buildTree(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
    }


我在这里要详细说明一下这个递归函数的各个参数及作用
第一个参数:就是前序遍历的vector,没有太多需要解释的
第二个参数:preStart,就是在子问题种前序的起始位置。详细的说,就是我们在确定根以后,我们就要递归左右子树,左右子树的起始位置是哪里就要确定。
第三个参数:preEnd:就是在子问题种前序的终止位置,这样就保证preStart与preEnd之间是子问题的结点序列。
第四个参数就是中序遍历的vector
第五个参数:inStart,就是在子问题中中序遍历的起始位置
第六个参数:inEnd,就是在子问题种中序遍历的结束位置


(2)递归函数
        TreeNode* _buildTree(vectorint>& preorder,int preStart,int preEnd,vectorint>&inorder,int inStart,int inEnd)
    {
        if(preStart>preEnd)
        {
            return nullptr;
        }
        //我们可以直接确定根节点,所以我们首先创建出根节点
        TreeNode* root = new TreeNode(preorder[preStart]);
        //找到根节点后,我们拿着根节点的值在中序遍历中找到对应位置,区分左右子树
        for(int i=inStart;iinEnd;i++)
        {
                //找到根节点所在的中序遍历的位置
            if(inorder == preorder[preStart])
            {
                    //由于递归函数完成子问题树的构建,所有让大问题的root左右子树分别链接即可
                root->left = _buildTree(preorder,preStart+1,preStart+i-inStart,inorder,inStart,i-1);
                root->right = _buildTree(preorder,preStart+i-inStart+1,preEnd,inorder,i+1,inEnd);
            }
        }
        return root;
    }

参数区间的决定

关键就是在递归子问题的时候传参数是多少。



size:size是左子树中的结点个数所以size = i-inStart
所以:root->left = _buildTree(preorder,preStart+1,preStart+i-inStart,inorder,inStart,i-1);

xxxxxx
root->right = _buildTree(preorder,preStart+i-inStart+1,preEnd,inorder,i+1,inEnd);
读者自行比较即可理解


递归结束的条件

接下来就是判断如何结束递归,就是递归函数中的第一个if。之前我们提到过,如果子问题子树的区间不存在就可以结束循环了,那么怎么才叫不存在呢?
我们刚刚获得了每一个子树的前序的范围【preStart,preEnd】,如果preStart==preEnd时候,就说明子树还有一个结点,仍然需要循环,但是有没有可能preStart>preEnd呢?答案是肯定的。我们发现递归子问题的时候preStart = preStart+1,preStart不断增大,而递归子问题时preEnd = preStart+size-1。
分析比较得:当子树只有一个结点(size == 1)是,preStart == preEnd。再递归一次后,size == 0,因此preStart > preEnd。就说明没有子树了,可以返回nullptr了。
所以得到代码:if (preStart>preEnd) return nullptr;


总结
xxxx
看到二叉树问题,我们首相应该想到的就是函数递归,因而二叉树具有很好的“递归特性”,每一个子树都是二叉树,都满足树的特性,子问题具有一样的特性就可以使用递归算法。其次我们应该明确知道,二叉树的“前、中、后,层序遍历”,并且知道他们之间的关系联系以及区别。在有以上的思想以及储备知识后,我们就可以写出具有一定思路的代码逻辑。这道题还有一个比较重要的地方就是控制子问题的前序、中序vector的范围界限。真正保证子问题与原问题的统一

xxxx
这就是这道题的完整解析,如果大家有更好的思路,或者我代码中可优化的地方,请指出,我一定虚心学习。希望我们一起学习,一起进步!!
回复

使用道具 举报

0

主题

595

帖子

-578

积分

限制会员

积分
-578
发表于 2021-9-13 09:01:58 | 显示全部楼层
帮你顶下哈!!
回复

使用道具 举报

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

本版积分规则

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

GMT+8, 2021-9-22 00:58 , Processed in 0.187201 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2021 Comsenz Inc.

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