105. 从前序与中序遍历序列构造二叉树

时间：2020-04-06 18:58:33 阅读：65 评论：0 收藏：0 [点我收藏+]

技术分享图片由前序排列和中序排列，返回一个二叉树

收获：

　　1.如果返回结果是树结构，那么需要返回根节点　　

　　2.在用递归构造一棵树的时候，结构都是：

　　　　1）node = Treenode ( val )

　　　　2) node.left = helper( )　

　　　　3) node.right = helper( )

　　3. 判断base case的时候，不满足要返回None，可参考TreeNode的定义

　　　　1）例如 if left > right : return None

　　4.开心，自己借鉴108题的思路直接一遍通过

　　　　技术分享图片

代码：

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

from collections import defaultdict

class Solution:

def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:

def helper(in_left,in_right):

if in_right<in_left or not preorder:

return None

node = TreeNode(preorder[0])

indexOfNode = inorder.index(preorder[0])

if preorder:

del preorder[0]

node.left = helper(in_left,indexOfNode-1)

node.right = helper(indexOfNode+1,in_right)

return node

return helper(0,len(inorder)-1)

原文：https://www.cnblogs.com/ChevisZhang/p/12643428.html

踩

(1)

评论一句话评论（0）

分享档案

更多>