手机网站开发人员工具,有没有免费装修设计的网站,wordpress标签关联,西安注册公司需要几天前言
二叉搜索树#xff0c;写了一道题#xff0c;第二题没写出来。明天再写吧。。。
内容
一、二叉搜索树中的搜索
700. 二叉搜索树中的搜索
给定二叉搜索树#xff08;BST#xff09;的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。…前言
二叉搜索树写了一道题第二题没写出来。明天再写吧。。。
内容
一、二叉搜索树中的搜索
700. 二叉搜索树中的搜索
给定二叉搜索树BST的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在则返回 null 。
递归
二叉搜索树也称二叉排序树或二叉查找树
若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉搜索树
时间复杂度O(N)其中 N 是二叉搜索树的节点数。最坏情况下二叉搜索树是一条链且要找的元素比链末尾的元素值还要小大这种情况下我们需要递归 N 次。
空间复杂度O(N)。最坏情况下递归需要 O(N) 的栈空间。
func searchBST(root *TreeNode, val int) *TreeNode {if rootnil{return root}if root.Valval{return root}if root.Valval{// result: searchBST(root.Left,val)// return resultreturn searchBST(root.Left,val)}//习惯直接写 searchBST(root.left, val)却忘了递归函数还有返回值
// result:searchBST(root.Right,val)
// return resultreturn searchBST(root.Right,val)
}
迭代
节点的有序性就帮我们确定了搜索的方向
时间复杂度O(N)其中 N 是二叉搜索树的节点数。最坏情况下二叉搜索树是一条链且要找的元素比链末尾的元素值还要小大这种情况下我们需要递归 N 次。
空间复杂度O(1)。没有使用额外的空间。
func searchBST(root *TreeNode,val int)*TreeNode{for root!nil{if root.Valval{rootroot.Left}else if root.Valval{rootroot.Right}else{return root}}return nil
}
最后
怎么写了十天的递归迭代遇到题还是写不出来。。。沉淀
