网站怎么设置支付,宁波58同城网,网络营销的概念与含义谷歌,百度手机网站优化指南leetcode 700 二叉搜索树中的搜索
给定二叉搜索树#xff08;BST#xff09;的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在#xff0c;则返回 null 。 示例 1: 输入#xff1a;root [4,2,7,1,…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, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution(object):def searchBST(self, root, val)::type root: TreeNode:type val: int:rtype: TreeNodechildRoot 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 childRootleetcode 450 删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key删除二叉搜索树中的 key 对应的节点并保证二叉搜索树的性质不变。返回二叉搜索树有可能被更新的根节点的引用。
一般来说删除节点可分为两个步骤
首先找到需要删除的节点如果找到了删除它。 示例 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
输出: [] 写不出来直接看评论题解了
这个方法最妙的地方就是把要删除的节点看成根节点
然后以目标节点为根分情况
无左右子树直接删除只有左子树左子树的根节点作为该结点只有右子树右子树的根节点作为该结点左右子树都有找到右子树中最小的结点记为rMin将rMin在右子树中删除用rMin代替root把root.left赋给rMin.leftroot.right赋给rMin.right
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution(object):def deleteNode(self, root, key)::type root: TreeNode:type key: int:rtype: TreeNodeif 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
