Python算法练习 10.28

leetcode 700 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

示例 1:

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

示例 2:

输入：root = [4,2,7,1,3], val = 5
输出：[]

 输出这么写我总以为是返回子树值的列表，结果是直接返回子树根节点

原来二叉搜索树就是二叉排序树，然而我直接暴力深搜。。。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def searchBST(self, root, val):""":type root: TreeNode:type val: int:rtype: TreeNode"""childRoot = Nonedef nextLevel(root, val):if root.val == val:return rootif root.left:targetLeft = nextLevel(root.left, val)if targetLeft:return targetLeftif root.right:targetRight = nextLevel(root.right, val)if targetRight:return targetRightreturn Noneif root.val == val:return rootif root.left:childRoot = nextLevel(root.left, val)if not childRoot and root.right:childRoot = nextLevel(root.right, val)return childRoot

 leetcode 450 删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

1. 首先找到需要删除的节点；
2. 如果找到了，删除它。

示例 1:

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2:

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点

示例 3:

输入: root = [], key = 0
输出: []

写不出来，直接看评论题解了

这个方法最妙的地方就是把要删除的节点看成根节点

然后以目标节点为根，分情况：

1. 无左右子树：直接删除
2. 只有左子树：左子树的根节点作为该结点
3. 只有右子树：右子树的根节点作为该结点
4. 左右子树都有：找到右子树中最小的结点（记为rMin），将rMin在右子树中删除，用rMin代替root，把root.left赋给rMin.left，root.right赋给rMin.right

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def deleteNode(self, root, key):""":type root: TreeNode:type key: int:rtype: TreeNode"""if not root:return Noneif key == root.val:if not (root.left or root.right):return Noneelif not root.left:return root.rightelif not root.right:return root.leftelse:rMin = root.rightwhile rMin.left:   #找到右子树里的最小值节点放到要删除的节点去rMin = rMin.leftrMin.right = self.deleteNode(root.right, rMin.val)   #删除原来右子树里的最小值节点rMin.left = root.leftreturn rMinif key < root.val:root.left = self.deleteNode(root.left, key)if key > root .val:root.right = self.deleteNode(root.right,key)return root