题目简介
654:最大二叉树
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点，其值为 nums 中的最大值。
递归地在最大值 左边 的 子数组前缀上 构建左子树。
递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。
617:合并二叉树
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
700:二叉搜索树中的搜索
给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null
98:验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
初见思路
复盘思路
- 参考从前序和中序遍历二叉树，每次找到最大点位置然后构建二叉树即可
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
if not nums:
return None
root_val = sorted(nums)[-1]
root = TreeNode(root_val)
max_idx = nums.index(root_val)
root.left = self.constructMaximumBinaryTree(nums[:max_idx])
root.right = self.constructMaximumBinaryTree(nums[max_idx+1:])
return root
- 按照题目意思来即可
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
node = None
if not root1:
return root2
elif not root2:
return root1
else:
node = TreeNode(root1.val+root2.val)
node.left = self.mergeTrees(root1.left, root2.left)
node.right = self.mergeTrees(root1.right, root2.right)
return node
- 层序遍历，YYDS.
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root:
return None
queue = collections.deque([root])
while queue:
size = len(queue)
for _ in range(size):
node = queue.popleft()
if node.val == val:
return node
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
return None
- 直接按题目意思来，可以直接解决
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
return self.isValid(root,float('-inf'),float('inf'))
def isValid(self,root,left_val,right_val) -> bool:
if not root:
return True
if root.val <= left_val or root.val >= right_val:
return False
return self.isValid(root.left , left_val, root.val) and self.isValid(root.right, root.val, right_val)
重点难点
https://programmercarl.com/0654.%E6%9C%80%E5%A4%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html
https://programmercarl.com/0617.%E5%90%88%E5%B9%B6%E4%BA%8C%E5%8F%89%E6%A0%91.html
https://programmercarl.com/0098.%E9%AA%8C%E8%AF%81%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
