重建二叉树

重建二叉树

http://www.nowcoder.com/questionTerminal/8a19cbe657394eeaac2f6ea9b0f6fcf6

python3
采用递归思想,思路:由前序遍历可知第一个节点即为根结点,然后将此节点对应在中序节点的位置将中序遍历分为左右子树,重新得到子树的前序,中序遍历,依次递归给下一层.

class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if len(tin) == 0:
            return None
        root = TreeNode(pre[0])            #前序遍历第一个值为根节点
        index = tin.index(root.val)        #因为没有重复元素,所以可以直接根据值来查找根节点在中序遍历中的位
        root.left = self.reConstructBinaryTree(pre[1:index+1],tin[:index])
        root.right = self.reConstructBinaryTree(pre[index+1:],tin[index+1:])
        return root
全部评论

相关推荐

头顶尖尖的程序员:我也是面了三四次才放平心态的。准备好自我介绍,不一定要背熟,可以记事本写下来读。全程控制语速,所有问题都先思考几秒,不要急着答,不要打断面试官说话。
点赞 评论 收藏
分享
认真搞学习:28小登的建议,投算法岗不要写什么物理竞赛,互联网+,多写点项目,用什么算法做了什么。还有本科算法是不可能的开发你这个也没有项目啊
点赞 评论 收藏
分享
评论
5
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务