654. 最大二叉树
题目简述：
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点，其值为 nums 中的最大值。
递归地在最大值 左边 的 子数组前缀上 构建左子树。
递归地在最大值 右边 的 子数组后缀上 构建右子树。
思路
利用递归
1. 创建root，类型为TreeNode，值为传入数组中的最大值
2. 设置它的左右节点为递归函数的返回值，递归函数的输入为一个区间范围
3. 设置停止条件，当left>=right，区间内不在有数值，返回None
代码如下：
class Solution: def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]: def dfs(left,right): if left>=right: return None max_num=max(nums[left:right]) index_max=nums.index(max_num) root=TreeNode(max_num) root.left=dfs(left,index_max) root.right=dfs(index_max+1,right) return root root=dfs(0,len(nums)) return root
利用字典来存储数组中各个数的下标值，貌似能跑得更快
class Solution: def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]: dict={} n=len(nums) for i in range(n): dict[nums[i]]=i def dfs(left,right,array): if left>=right: return None max_nums=max(array) max_index=dict[max_nums] root=TreeNode(max_nums) root.left=dfs(left,max_index,nums[left:max_index]) root.right=dfs(max_index+1,right,nums[max_index+1:right]) return root ptr1=dfs(0,n,nums) return ptr1
巧妙方法：单调栈实现
1. 一次遍历实现，一边遍历一边创建节点并设置左右孩子
class Solution: def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]: stack=[] for num in nums: cur=TreeNode(num) while stack and stack[-1].val<num: cur.left=stack.pop() if stack:# mean stack[-1].val>num stack[-1].right=cur # 运行至此，意味着stack为空 或者 stack不为空但是stack[-1].val>num并设好了对应右指针参数，此时可以把num加进stack中
stack.append(cur) return stack[0]
2. 先创建两个列表，分别存有左边和右边第一个更大值的信息，相当于两个单调栈，然后再重新遍历组建树
class Solution: def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]: n = len(nums) stk = list() left, right = [-1] * n, [-1] * n tree = [None] * n for i in range(n): # 每遍历一个值，都创建一个节点 tree[i] = TreeNode(nums[i]) while stk and nums[i] > nums[stk[-1]]: # 对于下标为stk[-1]的元素，右边第一个比他大的元素的下标为i，这是典型的单调栈 right[stk[-1]] = i stk.pop() if stk: # 对于下标为i的元素，左边第一个比他大的元素的下标为stk[-1]，这是典型的单调栈 left[i] = stk[-1] stk.append(i) root = None for i in range(n): if left[i] == right[i] == -1: root = tree[i] # 1. right[i]==-1 and left[i]!=-1，意味着nums[i]是只有左边有比他大的值或者nums[i]在最右边 # 2. 或者right[i]!=-1 and left[i]!=-1，并且nums[left[i]] < nums[right[i]])，意味着左右都有比他大的，且左边的小于右边的，右边有更大值 elif right[i] == -1 or (left[i] != -1 and nums[left[i]] < nums[right[i]]): # 先不管，就令左边最大值的右孩子为当前下标对应节点 tree[left[i]].right = tree[i] # 1. right[i]!=-1 and left[i]==-1，右边有更大的值，左边却没有。 else: # 此时把右边最大值的左孩子设为当前节点 tree[right[i]].left = tree[i] return root
617. 合并二叉树
题目简述：
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
思路：
利用层序遍历，挨个相加即可，对节点存在与否进行细致分类讨论
class Solution: def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode: if not t1: return t2 if not t2: return t1 merged = TreeNode(t1.val + t2.val) queue = collections.deque([merged]) queue1 = collections.deque([t1]) queue2 = collections.deque([t2]) while queue1 and queue2: node = queue.popleft() node1 = queue1.popleft() node2 = queue2.popleft() left1, right1 = node1.left, node1.right left2, right2 = node2.left, node2.right if left1 or left2: if left1 and left2: left = TreeNode(left1.val + left2.val) node.left = left queue.append(left) queue1.append(left1) queue2.append(left2) elif left1: node.left = left1 elif left2: node.left = left2 if right1 or right2: if right1 and right2: right = TreeNode(right1.val + right2.val) node.right = right queue.append(right) queue1.append(right1) queue2.append(right2) elif right1: node.right = right1 elif right2: node.right = right2 return merged
700. 二叉搜索树中的搜索
题目简述：
给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
思路：
递归实现
class Solution: def searchBST(self, root: TreeNode, val: int) -> TreeNode: if root is None: return None if val == root.val: return root return self.searchBST(root.left if val < root.val else root.right, val)
98. 验证二叉搜索树
题目简述：
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
思路：
递归：
1. 一个树要是二叉搜索树，那么对于他的一个节点来说，节点的值必须大于左孩子值小于右孩子值并且左孩子和右孩子都得是二叉搜索树
class Solution: def isValidBST(self, root: TreeNode) -> bool: def helper(node, lower = float('-inf'), upper = float('inf')) -> bool: if not node: return True val = node.val if val <= lower or val >= upper: return False if not helper(node.right, val, upper): return False if not helper(node.left, lower, val): return False return True return helper(root)
遍历，中序遍历
1. 二叉搜索树的中序遍历是单调递增的，利用这个性质
class Solution: def isValidBST(self, root: TreeNode) -> bool: stack, inorder = [], float('-inf') while stack or root: while root: stack.append(root) root = root.left root = stack.pop() # 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树 if root.val <= inorder: return False inorder = root.val root = root.right return True
总结：
1. 熟练掌握递归
2. 了解单调栈
3. 熟练掌握各种遍历