二叉树bst

二叉搜索树的中序遍历结果有序 ，二叉搜索树性质，左小右大，二叉搜索树中序遍历的结果应该是从小到大的。

题目描述二叉树是从上到下，从左到右描述，并非前中后序中的一种。

99. 恢复二叉搜索树

class Solution:first = None second = None prev = TreeNode(float('-inf')) #这样对类进行初始化也是可以的,函数中要使用用self.调用     实例属性，实例方法def recoverTree(self, root: Optional[TreeNode]) -> None:"""Do not return anything, modify root in-place instead."""  #原地修改，不要返回self.inorderTraverse(root)temp = self.first.val self.first.val = self.second.val self.second.val = temp def inorderTraverse(self, root):if root is None:return self.inorderTraverse(root.left)if root.val < self.prev.val:if self.first is None:self.first = self.prevself.second = root #本应该递增，变成了递减    打草稿可知道位置在哪self.prev = root #中序位置，更新结点   #由于更换了位置，第一个不符合条件的位于指针的prev位置，第二个不符合条件的位于root位置self.inorderTraverse(root.right)

669. 修剪二叉搜索树

class Solution:# 定义：删除 BST 中小于 low 和大于 high 的所有节点，返回结果 BSTdef trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:if root is None:return Noneif root.val < low:# 直接返回 root.right# 等于删除 root 以及 root 的左子树return self.trimBST(root.right, low, high)if root.val > high:# 直接返回 root.left# 等于删除 root 以及 root 的右子树return self.trimBST(root.left, low, high)# 闭区间 [lo, hi] 内的节点什么都不做,题目给的是闭区间  分解问题解法root.left = self.trimBST(root.left, low, high)root.right = self.trimBST(root.right, low, high)return root

明确了递归函数的定义之后进行思考，如果一个节点的值没有落在 [lo, hi] 中，有两种情况：

1、root.val < lo，这种情况下 root 节点本身和 root 的左子树全都是小于 lo 的，都需要被剪掉。

2、root.val > hi，这种情况下 root 节点本身和 root 的右子树全都是大于 hi 的，都需要被剪掉。

671. 二叉树中第二小的节点

class Solution:def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:if root.left is None and root.right is None:return -1 #只有一个结点，肯定没有第二小结点，  base case left ,right = root.left.val, root.right.val if root.val == root.left.val:left = self.findSecondMinimumValue(root.left) #在左边找第二小的节点值if root.right == root.right.val:right = self.findSecondMinimumValue(root.right) #在右边找第二小的节点值if left == -1:  #只要一边是叶子节点，就返回另一边找到的第二小值就可以 在最后在进行一个比较return rightif right == -1:return left return min(left,right) 

把题目理解清楚，把解决问题，定义的函数解决清楚，弄明白分解问题逻辑

这种自底向上的处理方式确保了我们在处理每个节点时，已经拥有了其左右子树的所有信息，可以直接进行计算，而不需要重复访问子树，从而提高了效率。 后序位置的优势、 后序遍历是“自底向上”的遍历方式，即：

1. 先递归地遍历左子树，
2. 再递归地遍历右子树，
3. 最后处理当前节点（根节点）。

这种遍历方式意味着我们在处理一个节点时，已经处理并得到它的左右子树的结果。 “自底向上”的处理方式指的是在后序遍历过程中，我们在处理一个节点时，已经处理并完成了其所有子节点的操作。换句话说，当我们处理一个节点时，左右子树已经完全处理完毕，我们可以直接利用这些子树的结果进行进一步的计算。

在剪枝问题中，后序遍历是一种非常有效的方法，因为它可以确保在处理一个节点之前，已经处理完它的左右子树。这意味着我们可以从叶子节点开始，逐层向上剪枝，而不会影响未处理的节点。具体来说，后序遍历的顺序是“左子树 -> 右子树 -> 根节点”，这让我们能够自底向上地处理和剪枝。下面我们详细解释一下为什么后序遍历位置可以实现这种高效的剪枝 在整个过程中，我们每次处理节点时，都能确保它的左右子树已经处理完毕，这样我们可以根据子树的结果决定是否剪掉当前节点。这种方法确保了我们不会遗漏任何需要剪掉的节点，并且不会重复处理已经剪掉的部分，达到了最高的效率。

814. 二叉树剪枝

class Solution:def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:#定义，输入二叉树，返回二叉树叶子节点都是1if root is None:return None root.left = self.pruneTree(root.left)root.right = self.pruneTree(root.right)  #是用分解问题的思路来做#后序位置的优越性，自下而上的处理方式，处理根节点时，左右结点已经处理if root.val ==  and root.left is None and root.right is None:return None #只有从后续遍历位置  并且要一直减枝return root 

生成二叉树的题目，无非就是先生成根节点，然后递归生成左右子树，最后把根节点和左右子树连接起来。具体区别在于你如何找到根节点，如何划分左右子树。

1008. 前序遍历构造二叉搜索树

class Solution:def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:return self.build(preorder, 0, len(preorder) - 1)#定义：将preorder[start, end]区间内的元素生成bst，并且返回根节点def build(self, preorder, start, end) :if start > end:return None rootVal = preorder[start]root = TreeNode(rootVal)#p是左右子树的分界点      要构造树p = start + 1 while p <= end and preorder[p] < rootVal:p += 1   #找到第一个>根节点的值root.left = self.build(preorder, start + 1, p - 1)root.right = self.build(preorder ,p, end) return root