讨论/技术交流/求助各位大佬,力扣105题。困扰萌新很久了。/
求助各位大佬,力扣105题。困扰萌新很久了。

求助各位大佬。力扣105题https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/为什么我直接用index作为参数传入就会出错,而传入起点+左子树长度就没事,这个问题困扰我好几天了,一直想不明白,现在都是背住的。人肉记题器......

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def recur(preorder,pre_start,pre_end,inorder,in_start,in_end):
            if pre_start > pre_end:
                return None
            root = preorder[pre_start] #val
            root_node = TreeNode(root)
            root_idx = inorder.index(root) # 0
            #print('left:',pre_start+1,root_idx)
            left = recur(preorder,pre_start+1,root_idx,inorder,in_start,root_idx-1)#这里为什么不能直接用 root_idx ???
                                                                                    #root_index不是每次左子树的结束点吗?
            #print('right:',root_idx+1,pre_end)
            right = recur(preorder,root_idx + 1,pre_end,inorder,root_idx+1,in_end)
            root_node.left = left
            root_node.right = right
            return root_node
        length = len(preorder)-1
        if length < 0:
            return 
        return recur(preorder,0,length,inorder,0,length)
共 15 个回复

哦哦哦,这样子的嗦。也很厉害了。

image.png

之前打的草稿,你凑合看看吧

我只是一道题做完之后还会改来改去而已

就是划分左右区间来着。你可以自己画图看看。

老哥,还有个题外问题。你一天提交300多次是怎么做到的,一天1440分钟,4分钟一道题。太牛逼了吧。哈哈哈

老哥,感谢解答。这种写法我背住了,这是我第二次刷了,上次没怎么思考,跟你写的一样。这次深入思考发现出问题了......

老哥,不愧是犯过同样错误的人,一针见血,牛!结合下面那个老哥的图,我懂了,感谢~

大佬,我借着你的图和上面那个哥们的话,懂了。通过inorder定位的root_index,在preorder中对应的索引左边的元素个数确实是等于以该root为根的左子树的大小,但是序号错开了。比如以 2 为根的节点.在inorder中的索引是 3 ,对应到preorder中是元素 8 ,元素 2 的左子树有3个,而如果我在preorder中截取prestart+1,root_indx的话,就只能取到4和8两个元素。所以应该按长度来取。懂了懂了,感谢大佬。

这里的inIndex还可以写成inL + leftSize + 1

leetcode还支持可视化吗 这么牛逼