企业怎么建设自己的网站首页,wordpress百度熊掌号,孝感新闻门户网站,wordpress 获取当前路径235. 二叉搜索树的最近公共祖先 本题思路#xff1a; 还是要利用二叉搜索树的特性#xff0c;中序遍历为有序数组。如果pq两个节点都小于root#xff0c;那么最近公共祖肯定是在他的左子树#xff0c;如果都大于那么#xff0c;肯定就在右子树。然后直接return root
代码…235. 二叉搜索树的最近公共祖先 本题思路 还是要利用二叉搜索树的特性中序遍历为有序数组。如果pq两个节点都小于root那么最近公共祖肯定是在他的左子树如果都大于那么肯定就在右子树。然后直接return root
代码 def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode:if p.valroot.val and q.valroot.val:return self.lowestCommonAncestor(root.left,p,q)if p.valroot.val and q.valroot.val:return self.lowestCommonAncestor(root.right,p,q)return root 701. 二叉搜索树中的插入操作 本题目涉及到一个二叉搜索树树的插入操作如果当root等于none的时候实际上我们这里就要开始插入操作了因为我们对二叉搜索树的特性有了解如果这个val根节点的话它一定会被插到左子树中去所以当root等于none的时候也就是这个节点应该放的位置 这 里直接return treenode(val)就可以了。然后分别对左子树和右子树进行递归这里是需要用root.leftaroot.right来接收左右孩子的值的。所以这里是一个典型的 递归函数需要变量接受返回值 450. 删除二叉搜索树中的节点 思路这道题吧 面试如果考这个 我就直接g了。。。。
有以下五种情况
第一种情况没找到删除的节点遍历到空节点直接返回了找到删除的节点 卡哥给的动画 直接秒懂from 代码随香录 第二种情况左右孩子都为空叶子节点直接删除节点 返回NULL为根节点第三种情况删除节点的左孩子为空右孩子不为空删除节点右孩子补位返回右孩子为根节点第四种情况删除节点的右孩子为空左孩子不为空删除节点左孩子补位返回左孩子为根节点第五种情况左右孩子节点都不为空则将删除节点的左子树头结点左孩子放到删除节点的右子树的最左面节点的左孩子上返回删除节点右孩子为新的根节点。 代码 def deleteNode(self, root: Optional[TreeNode], key: int) - Optional[TreeNode]:if not root:return Noneif root.valkey:#如果是叶子节点if root.leftNone and root.rightNone:return None#左不空 右空elif root.left!None and root.rightNone:return root.left#左空 右不空elif root.leftNone and root.right!None:return root.right else:#左右都不空 选择让右孩子继位cur root.right while cur.left!None:cur cur.leftcur.left root.leftreturn root.right if key root.val:root.left self.deleteNode(root.left,key)if key root.val:root.right self.deleteNode(root.right,key)return root
