本题需要注意的是切片操作，可以跟构造二叉树的切片操作对比。
需要注意：
1、构造二叉树只能使用前序遍历的方式；
2、被取出的数组元素（根节点）需要在切片操作的时候被排除；
3、循环不变量都是左闭右开区间。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def constructMaximumBinaryTree(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if not nums:
return None
max_val = max(nums)
max_index = nums.index(max_val)
node = TreeNode(max_val)
node.left = self.constructMaximumBinaryTree(nums[:max_index])
node.right = self.constructMaximumBinaryTree(nums[max_index + 1 : ])
return node1、在遍历一个单独的树的时候，终止return None，但是对于两个合并的情况，需要在一棵遍历结束之后转到另外一棵。?相当于“嫁接”
2、返回值选择一棵主要遍历的树。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def mergeTrees(self, root1, root2):
"""
:type root1: TreeNode
:type root2: TreeNode
:rtype: TreeNode
"""
# 终止条件：在一棵遍历到末端的时候转到另外一棵
if not root1:
return root2
if not root2:
return root1
# 中间更新：节点值相加
root1.val += root2.val
# 递归调用：以root1作为输出的结果
root1.left = self.mergeTrees(root1.left, root2.left)
root1.right = self.mergeTrees(root1.right, root2.right)
return root1本题给出两种（递归、迭代）?方法。
1、递归需要新建一个节点result来接收每次递归的返回值；
2、搜索二叉树BST满足左侧小，右侧大的条件，所以搜索顺序已经被固定，不需要考虑采用何种搜索顺序；
3、推荐使用迭代。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def searchBST(self, root, val):
"""
:type root: TreeNode
:type val: int
:rtype: TreeNode
"""
# 迭代
while root:
if root.val == val:
break
elif root.val > val:
root = root.left
else:
root = root.right
return root
# 递归
result = TreeNode(None) # 新建一个用来储存每次递归返回值的节点
# 种植条件：空节点or找到该值的节点
if not root or root.val == val:
return root
# 中间更新：小于节点值到右侧找，大于节点值到左侧找
if root.val > val:
result = self.searchBST(root.left, val)
if root.val < val:
result = self.searchBST(root.right, val)
# 返回值：找到的节点
return result将二叉树按照中序遍历（左-中-右）保存到一个数组，按照BST的定义现在数组是按照严格单调递增的顺序保存的（等于也是不满足的）。只需要在数组里for循环比较后者是不是大于前者即可。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
# 数组保存BST + 递归
def __init__(self):
self.vec = []
def traversal(self, node):
if not node:
return
self.traversal(node.left)
self.vec.append(node.val) # 先找到最左端，每次依次先保存左子树的值，然后是右子树
self.traversal(node.right)
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
self.vec = [] # 清空数组
self.traversal(root)
for i in range(1, len(self.vec)): # 需要从1开始
if self.vec[i - 1] >= self.vec[I]: # 注意：等于也是不满足
return False
return True 设置全局的最小值（注意！题干给出最小值的下界是int的最小值，所以需要使用float的最小值来初始化）。
和上面方法一样，在遍历的过程中，不断更新max的值，使其始终保持是最大值。
返回结果是中间节点左右的交集，那么只要有一个是false则递归返回到root节点就是fasle。
def __init__(self):
self.max_value = float('-inf') # 因为题干最小值可能是int的最小值
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
# 递归（设定最小值）
if not root:
return True # 空树也是BST
left = self.isValidBST(root.left) # 向左遍历，返回值是bool
# 更新max值：
if root.val > self.max_value: # 如果当前节点的值比max大，那么赋值给max，保持max是现在最大的值
self.max_value = root.val
else: # 不满足直接返回false
return False
right = self.isValidBST(root.right) # 向右遍历，返回值是bool，逻辑和上面的一样
return left and right # root节点返回值是left和right的交集一个全局的指针pre指向上一个root节点，一个指针在递归函数里指向当前的root节点，保持root的值始终大于pre。
和保存到数组后用for处理比较像，但是可以直接在BST中处理，不需要单独开内存。
def __init__(self):
self.vec = []
self.max_value = float('-inf') # 因为题干最小值可能是int的最小值
self.pre = None
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
# 记录比较前一个节点
if not root:
return True
left = self.isValidBST(root.left)
# 双指针思路，一个指向当前的root，一个保存的是上一个遍历的root的pre，保持root的值始终大于pre的值
if self.pre is not None and self.pre.val >= root.val: # not None是因为初始化pre为None需要在赋值之后才可以比较val
return False
self.pre = root
right = self.isValidBST(root.right)第19天完结🎉