落的太多，竟然忘记了第17天是个休息日
1.654. 最大二叉树
题目链接：654. 最大二叉树
文档讲解： 代码随想录
我自己写的代码，直接调用max函数找到最大值，然后进行切割递归。
class Solution(object):
def constructMaximumBinaryTree(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
#终止条件：树为空
if not nums:
return None
#找到最大值为根节点
root_val = max(nums)
root = TreeNode(root_val)
#找到切割点
separator_index = nums.index(root_val)
#切割
nums_left = nums[:separator_index]
nums_right = nums[separator_index + 1:len(nums)]
#递归
root.left = self.constructMaximumBinaryTree(nums_left)
root.right = self.constructMaximumBinaryTree(nums_right)
return root
标答思路：终止条件，在数组中只有一个元素的时候构造一个新节点返回；单层逻辑，找到数组中最大值以及对应的下标，根据下标左区间构造左子树，需要判断最大值下标大于0，以确保左子树至少有一个值，同理，要判断最大值下标小于数组长度减一，以确保右子树至少有一个值。
class Solution(object):
def constructMaximumBinaryTree(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if len(nums) == 1:
return TreeNode(nums[0])
node = TreeNode(0)
max_value = 0
max_index = 0
for i in range(len(nums)):
if nums[i] > max_value:
max_value = nums[i]
max_index = i
node.val = max_value
if max_index > 0:
nums_left = nums[:max_index]
node.left = self.constructMaximumBinaryTree(nums_left)
if max_index < len(nums) - 1:
nums_right = nums[max_index + 1:len(nums)]
node.right = self.constructMaximumBinaryTree(nums_right)
return node
class Solution(object):
def constructMaximumBinaryTree(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
return self.traversal(nums, 0, len(nums))
def traversal(self, nums, left, right):
#使用下标
if left >= right:
return None
max_index = left
for i in range(left + 1, right):
if nums[i] > nums[max_index]:
max_index = i
node = TreeNode(nums[max_index])
node.left = self.traversal(nums, left, max_index)
node.right = self.traversal(nums, max_index + 1, right)
return node
2.617.合并二叉树
题目链接：654. 最大二叉树
文档讲解： 代码随想录
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.left = self.mergeTrees(root1.left, root2.left)
root1.right = self.mergeTrees(root1.right, root2.right)
return root1
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
#新建一个node
node = TreeNode(0)
node.val = root1.val + root2.val
node.left = self.mergeTrees(root1.left,root2.left)
node.right = self.mergeTrees(root1.right, root2.right)
return node
迭代法：
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
queue = collections.deque()
queue.append(root1)
queue.append(root2)
while queue:
node1 = queue.popleft()
node2 = queue.popleft()
if node1.left and node2.left:
queue.append(node1.left)
queue.append(node2.left)
if node1.right and node2.right:
queue.append(node1.right)
queue.append(node2.right)
node1.val += node2.val
if not node1.left and node2.left:
node1.left = node2.left
if not node1.right and node2.right:
node1.right = node2.right
return root1
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
queue = deque()
queue.append((root1, root2))
while queue:
node1, node2 = queue.popleft()
node1.val += node2.val
if node1.left and node2.left:
queue.append((node1.left, node2.left))
elif not node1.left:
node1.left = node2.left
if node1.right and node2.right:
queue.append((node1.right, node2.right))
elif not node1.right:
node1.right = node2.right
return root1
3.700. 二叉搜索树中的搜索
题目链接：700. 二叉搜索树中的搜索
文档讲解： 代码随想录
class Solution(object):
def searchBST(self, root, val):
"""
:type root: TreeNode
:type val: int
:rtype: TreeNode
"""
if not root or root.val == val:
return root
res = TreeNode(None)
if val < root.val:
res = self.searchBST(root.left, val)
if val > root.val:
res = self.searchBST(root.right, val)
return res
迭代法：
class Solution(object):
def searchBST(self, root, val):
"""
:type root: TreeNode
:type val: int
:rtype: TreeNode
"""
while root:
if val < root.val:
root = root.left
elif val > root.val:
root = root.right
else:
return root
return None
使用栈遍历
class Solution(object):
def searchBST(self, root, val):
"""
:type root: TreeNode
:type val: int
:rtype: TreeNode
"""
stack = [root]
while stack:
node = stack.pop()
if node.val == val:
return node
if node.right:
stack.append(node.right)
if node.right:
stack.append(node.left)
return None
4.98.验证二叉搜索树
题目链接：98.验证二叉搜索树
文档讲解： 代码随想录
递归法，利用中序递增性质，转换成数组
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
vec = []
self.traversal(root, vec)
for i in range(1, len(vec)):
if vec[i] <= vec[i -1]:
return False
return True
def traversal(self, node, vec):
#中序递归遍历
if not node:
return
self.traversal(node.left, vec)
vec.append(node.val)
self.traversal(node.right, vec)
设定极小值，进行比较
class Solution(object):
def __init__(self):
self.max_val = float('-inf')
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
left = self.isValidBST(root.left)
if self.max_val < root.val:
self.max_val = root.val
else:
return False
right = self.isValidBST(root.right)
return left and right
这道题的两个陷阱：
（1）不能单纯的比较左节点小于中间节点，右节点大于中间节点。要比较的是左子树的所有节点都小于中间节点，右子树的所有节点都大于中间节点。
（2）建议避免初始化最小值，因此做出改进，取到最左面的节点数值来比较。
class Solution(object):
def __init__(self):
self.pre = None
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
left = self.isValidBST(root.left)
if self.pre and self.pre.val >= root.val:
return False
self.pre = root
right = self.isValidBST(root.right)
return left and right
迭代法
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
#题目中说明树中节点数目大于等于1
stack = []
cur = root
pre = None
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
if pre and pre.val >= cur.val:
return False
pre = cur
cur = cur.right
return True