Leetcode 654 最大二叉树
题目链接: 最大二叉树
给定一个不含重复元素的整数数组，据此构建一棵最大二叉树，方法如下:
- 找出该数组中最大的元素，为其创建一个相应二叉树节点。该元素将该数组分割成两个部分。
- 从左部分中选取其中最大的元素，作为当前节点的左孩子节点
- 从右部分中选取其中最大的元素，作为当前节点的右孩子节点，重复上述操作直至处理完数组中所有元素。
思路: 整理上述流程，我们知道，我们需要不断找出数组片段中最大值，创建相应节点，并递归处理剩下的区间。
有了昨天处理 从中序遍历和后续遍历构造二叉树(Leetcode 106) 的经验，我们知道，传递区间最佳的方式不是再创建额外的数组，而是传递下标和原数组。因此此处我们采用传递下标的方式解决相应问题。
递归三部曲分析如下:
- 递归函数参数与返回值
递归函数参数为数组整体，以及用于分割数组的相应下标。返回值为创建好的相应二叉树节点 - 递归终止条件:
当给定区间为空时，终止遍历 - 每层递归操作:
找出区间内最大值，利用该最大值将区间分割成两个部分。并将这两个部分的返回值分别作为当前节点的左右子节点。
具体代码实现
class Solution:def buildMaximumBinaryTree(self, nums: List[int], startIdx: int, endIdx: int) -> Optional[TreeNode]:# 由于坚持左闭右开区间，因此当起始下标大于等于终止下标时，停止继续向下递归。if startIdx >= endIdx:return# 找出给定区间内的最大值maxIdx, maxElement = startIdx, nums[startIdx]for i in range(startIdx, endIdx):if nums[i] > maxElement:maxIdx, maxElement = i, nums[i]root = TreeNode(maxElement)leftStartIdx = startIdxleftEndIdx = maxIdxrightStartIdx = maxIdx + 1rightEndIdx = endIdxif leftEndIdx - leftStartIdx > 0:root.left = self.buildMaximumBinaryTree(nums, leftStartIdx, leftEndIdx)if rightEndIdx - rightStartIdx > 0:root.right = self.buildMaximumBinaryTree(nums, rightStartIdx, rightEndIdx)return rootdef constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:# 坚持左闭右开区间root = self.buildMaximumBinaryTree(nums, 0, len(nums))return rootLeetcode 617 合并二叉树
题目链接: 合并二叉树
给定两棵二叉树，将其中的节点进行合并，返回合并后二叉树的根节点。
Example1:
1 2 3/ \ / \ / \3 2 + 1 3 = 4 5/ \ \ / \ \
5 4 7 5 4 7
当对应节点均存在时，合并后节点的值相当于对应节点值之和
当对应节点存在一个时，合并后节点的值相当于存在的节点值
思路: 合并二叉树时，我们可以在其中一棵二叉树中对节点的值原地进行修改，完成修改后，直接返回对应二叉树的根节点即可。
通过递归三部曲进行分析:
- 递归函数参数以及返回值:
递归函数参数为当前正在遍历的两棵二叉树的对应节点，返回值应该为两棵二叉树合并后的节点 - 递归终止条件
正在遍历的两棵二叉树的相应节点均为空时，终止递归操作。 - 每层递归操作
若两棵二叉树的相应节点均存在，则将节点值相加，创建一个新节点。若仅一棵二叉树的相应节点存在，则在其中一棵二叉树的节点上原地进行修改。
具体代码实现
class Solution:def merge(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:# 对应节点均不存在，返回空if root1 is None and root2 is None:return# 两个节点均存在，将节点值相加if root1 and root2:root1.val += root2.valroot1.left = self.merge(root1.left, root2.left)root1.right = self.merge(root1.right, root2.right)return root1# 返回存在的相应节点if root1:return root1return root2def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:return self.merge(root1, root2)
Leetcode 700 二叉搜索树中的搜索
题目链接: 二叉搜索树中的搜索
在一棵给定的二叉搜索树中，检索给定的值是否出现过。若给定的值在二叉树中出现过则返回相应节点，否则返回空
思路: 首先复习二叉搜索树的概念。
二叉搜索树，即为根节点严格大于左子树中的所有节点，严格小于右子树中所有节点，且左右子树均递归地符合这一要求的一类二叉树。通过二叉搜索树搜索特定的值，时间复杂度为 O(logn)
利用递归三部曲进行分析:
- 递归函数参数与返回值:
递归函数参数为当前遍历的节点以及待查找的目标值，返回值为相应的二叉树节点 - 递归终止条件:
当前节点为空时，返回空节点，终止递归操作。 - 每层递归操作:
比较当前节点的值与目标值，若相等，则返回相应节点，若不相等，则继续深度递归。
具体代码实现
# 递归法
class Solution:def search(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:if root is None:returnif root.val > val:return self.search(root.left, val)if root.val < val:return self.search(root.right, val)return rootdef searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:return self.search(root, val)
# 迭代法
class Solution:def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:from collections import dequeif root is None:returnmyQueue = deque()myQueue.append(root)while myQueue:node = myQueue.popleft()if node.val == val:return node# 利用二叉搜索树中的特性，将相应节点加入到队列中if node.val > val and node.left:myQueue.append(node.left)if node.val < val and node.right:myQueue.append(node.right)return
Leetcode 98 验证二叉搜索树
题目链接: 验证二叉搜索树
给定一棵二叉树，判断该二叉树是否为二叉搜索树。
思路: 本题中一个常见的误区是，直接尝试使用递归法，通过左右子树是否满足二叉搜索树的条件，来判断以当前节点为根节点的二叉树是否为二叉搜索树。然而这种思路并不能够处理以下的情况:
5/ \4 6/ \3 7
由于 3 < 5，因此该二叉树不是二叉搜索树。
再回忆二叉树的特性，二叉树的根节点大于左子树中的所有节点，小于右子树中的所有节点。因此，我们可以尝试通过中序遍历，获取当前二叉树的数组。若当前二叉树确实是二叉搜索树，则该数组应该是严格递增的。因此，我们可以通过判断当前数组是否严格递增，来判断当前二叉树是否为二叉搜索树。
具体代码实现
class Solution:def inorderTraverse(self, cur: Optional[TreeNode]) -> List[int]:result = []myStack = []if cur is None:return resultmyStack.append([cur, False])while myStack:node, visited = myStack.pop()if visited:result.append(node.val)continueif node.right:myStack.append([cur.right, False])myStack.append([cur, True])if node.left:myStack.append([cur.left, False])return resultdef isValidBST(self, root: Optional[TreeNode]) -> bool:inorder = self.inorderTraverse(root)# 验证中序数组是否严格单调递增for i in range(1, len(inorder)):if inorder[i] <= inorder[i-1]:return Falsereturn True