- 1008. 前序遍历构造二叉搜索树
返回与给定前序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。
(回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，前序遍历首先显示节点 node 的值，然后遍历 node.left，接着遍历 node.right。）
题目保证，对于给定的测试用例，总能找到满足要求的二叉搜索树。
示例
输入：[8,5,1,7,10,12]
输出：[8,5,10,1,7,null,12]
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
def helper(lower = float('-inf'), upper = float… return root
idx = 0
n = len(preorder)
return helper()
- 105. 从前序与中序遍历序列构造二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder or not inorder:
return None
root = TreeNode(preorder[0]) #根节点为前序遍历第一个节点
index = inorder.index(preorder[0]) # 定位出中序遍历根节点的索引
root.left = self.buildTree(preorder[1:index+1], inorder[:index])
# 递归构建左子树，前序遍历左子树范围为，1~index,中序遍历左子树范围为0~index-1
root.right = self.buildTree(preorder[index+1:], inorder[index+1:])
# 递归构建右子树，前序遍历右子树范围为index之后，中序遍历右子树范围为index往后
return root
- 106. 从中序与后序遍历序列构造二叉树
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
if not inorder or not postorder:
return None
root = TreeNode(postorder[-1])
index = inorder.index(postorder[-1])
root.left = self.buildTree(inorder[:index],postorder[:index])
root.right = self.buildTree(inorder[index+1:],postorder[index:-1])
return root
889. 根据前序和后序遍历构造二叉树
返回与给定的前序和后序遍历匹配的任何二叉树。pre 和 post 遍历中的值是不同的正整数。
示例
输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]
1 <= pre.length == post.length <= 30
pre[] 和 post[] 都是 1, 2, ..., pre.length 的排列
每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def constructFromPrePost(self, pre: List[int], post: List[int]) -> TreeNode:
if not pre or not post:
return None
root = TreeNode(pre[0])
if len(pre) == 1:
return root
index = post.index(pre[1]) + 1 # 后序遍历右子树起始位置
root.left = self.constructFromPrePost(pre[1:index+1],post[:index])
root.right = self.constructFromPrePost(pre[index+1:],post[index:-1])
return root
- 108. 将有序数组转换为二叉搜索树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if not nums:
return
mid = len(nums) //2
root = TreeNode(nums[mid])
left = nums[:mid]
right = nums[mid+1:]
root.left = self.sortedArrayToBST(left)
root.right = self.sortedArrayToBST(right)
return root
