代码随想录算法训练营第20天 654.最大二叉树 617.合并二叉树 700.二叉搜索树中的搜索 98.验证二叉搜索树

**代码随想录算法训练营第20天**

## **654. 最大二叉树**

### 题目描述给定一个不含有0 的非负整数数组 `nums`，请你找出一个最大二叉树的高度。

假设输入的数组代表二叉树中的值，每个节点的值等于该子树中最大值。全局不改变数组 `nums`。

### 示例* 输入：`[3,2,1,6,0,5]`
* 输出：4*说明：最优解是 `[3,9,20,null,null,15,7]`

### 解决方案我们可以使用后序遍历（Postorder Traversal）来解决这个问题。这种方法首先访问叶子结点，然后回溯到父节点。

class Solution:
 def maxGain(self, nums):
 return self.postOrder(nums)

 def postOrder(self, nums):
 if not nums:
 return0 max_val = float('-inf')
 for num in nums:
 max_val = max(max_val, num)

 left_gain = self.postOrder([num for i, num in enumerate(nums) if i != len(nums)-1 and num < max_val])
 right_gain = self.postOrder([num for i, num in enumerate(nums) if i !=0 and num > max_val])

 return max(left_gain, right_gain) +1

## **617. 合并二叉树**

### 题目描述给定两个二叉树 `root1` 和 `root2`，其中 `root1` 的值均为非负整数，并且 `tree2` 中的每个值都加上 `root1` 中对应位置的值。请合并这两个二叉树。

### 示例* 输入：`[4,11,8,13,null,7,4]` 和 `[10,20,30,60,40,50]`
* 输出：`[54,73,38,96,83,97,0]`

### 解决方案我们可以使用前序遍历（Preorder Traversal）来解决这个问题。这种方法首先访问根结点，然后回溯到父节点。

class Solution:
 def mergeTrees(self, root1, root2):
 if not root1 and not root2:
 return None merged = TreeNode((root1.val if root1 else0) + (root2.val if root2 else0))
 merged.left = self.mergeTrees(root1.left if root1 else None, root2.left if root2 else None)
 merged.right = self.mergeTrees(root1.right if root1 else None, root2.right if root2 else None)

 return merged

## **700. 二叉搜索树中的搜索**

### 题目描述给定一个二叉搜索树（BST）的根结点 `root` 和一个值 `val`，请你在 BST 中查找 `val`。

如果 `val` 存在于 BST 中，则返回 True。否则，返回 False。

### 示例* 输入：`[2,1,3]` 和 `3`
* 输出：True*说明：在 BST 中找到值为3 的结点。
* 输入：`[2,1,3]` 和 `4`
* 输出：False*说明：在 BST 中找不到值为4 的结点。

### 解决方案我们可以使用中序遍历（Inorder Traversal）来解决这个问题。这种方法首先访问左子树，然后回溯到父节点。

class Solution:
 def searchBST(self, root: TreeNode, val: int) -> bool:
 if not root or root.val == val:
 return True if val < root.val:
 return self.searchBST(root.left, val)
 else:
 return self.searchBST(root.right, val)

## **98. 验证二叉搜索树**

### 题目描述给定一个二叉树的根结点 `root`，请你判断该树是否是二叉搜索树。

满足 BST 的条件：
* 每个结点的值都大于其左子树中所有结点的值。
* 每个结点的值都小于其右子树中所有结点的值。

### 示例* 输入：`[2,1,3]`
* 输出：True*说明：该树是二叉搜索树。
* 输入：`[5,1,4,null,3,6]`
* 输出：False*说明：该树不是二叉搜索树。

### 解决方案我们可以使用中序遍历（Inorder Traversal）来解决这个问题。这种方法首先访问左子树，然后回溯到父节点。

class Solution:
 def isValidBST(self, root: TreeNode) -> bool:
 self.prev = float('-inf')
 return self.inOrder(root)

 def inOrder(self, node):
 if not node:
 return True if not self.inOrder(node.left):
 return False if self.prev >= node.val:
 return False self.prev = node.val return self.inOrder(node.right)

以上是对应题目的解决方案和解释。