官方网站下载打印机的驱动,wordpress 404 not found,桂林建设银行招聘网站,怎样自己做网站235. 二叉搜索树的最近公共祖先
思想#xff1a;和二叉树的公共最近祖先节点的思路基本一致的#xff01;就是不用从下往上遍历处理#xff01;可以利用的二叉搜索树的特点从上往下处理了#xff01;而且最近公共节点肯定是第一个出现在【q#xff0c;p】这个区间的内的和二叉树的公共最近祖先节点的思路基本一致的就是不用从下往上遍历处理可以利用的二叉搜索树的特点从上往下处理了而且最近公共节点肯定是第一个出现在【qp】这个区间的内的 # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution:def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode:return self.lowestCommonAncestor1(root, p, q)def lowestCommonAncestor1(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode:# 二叉搜索树是有序的不同于二叉树的公共祖先需要从下往上遍历# 而且公共节点一定会出现在【pq】之前我们递归遍历最先出现在这个区间就是公共祖先节点了if root is None:return root# 处理中节点了if root.val q.val and root.val p.val: # 处理左节点left self.lowestCommonAncestor(root.left, p, q)if left is not None:# if not left: 这种用来判断节点不对的return leftif root.val q.val and root.val p.val:right self.lowestCommonAncestor(root.right, p, q)if right is not None:return rightreturn root701. 二叉搜索树中的插入操作
思路只要按照二叉搜索树的规则去遍历遇到空节点就插入节点就可以了!通过递归函数返回值完成了新加入节点的父子关系赋值操作了下一层将加入节点返回本层用root-left或者root-right将其接住 # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def insertIntoBST(self, root: Optional[TreeNode], val: int) - Optional[TreeNode]:if root is None:node TreeNode(val)# root nodereturn nodeif root.val val:root.left self.insertIntoBST(root.left, val) # 左if root.val val:root.right self.insertIntoBST(root.right, val) # 有# 中return root
450. 删除二叉搜索树中的节点
思路对于这种增删的使用root.left and root.right来接受返回的节点值的返回值来加入新节点 这里也可以通过递归返回值删除节点搜索树不用限定是用前中后序遍历根据搜索树有序规则遍历就好了但是还是要有递归三部曲的
确定单层递归的逻辑
这里就把二叉搜索树中删除节点遇到的情况都搞清楚。
有以下五种情况
第一种情况没找到删除的节点遍历到空节点直接返回了找到删除的节点 第二种情况左右孩子都为空叶子节点直接删除节点 返回NULL为根节点第三种情况删除节点的左孩子为空右孩子不为空删除节点右孩子补位返回右孩子为根节点第四种情况删除节点的右孩子为空左孩子不为空删除节点左孩子补位返回左孩子为根节点第五种情况左右孩子节点都不为空则将删除节点的左子树头结点左孩子放到删除节点的右子树的最左面节点的左孩子上返回删除节点右孩子为新的根节点。
第五种情况有点难以理解看下面动画 class Solution:def deleteNode(self, root, key):if root is None:return root# 单层逻辑if root.val key:if root.left is None and root.right is None:return Noneelif root.left is None:return root.rightelif root.right is None:return root.leftelse:cur root.rightwhile cur.left is not None:cur cur.leftcur.left root.leftreturn root.rightif root.val key: # 左root.left self.deleteNode(root.left, key)if root.val key: # 右root.right self.deleteNode(root.right, key)return root
