一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
Offer多多
Salarytics
交友
Learn
Who's Hiring?
Visa Tracker
疫情动态
指尖新闻
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 378|回复: 7
收起左侧

[树/链表/图] 加米lc 270, 求问closest binary search tree value思路

[复制链接] |只看干货 |树/链表/图, 刷题
我的人缘0

升级   3.29%


分享帖子到朋友圈
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (71)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
本帖最后由 超人96825 于 2020-8-10 12:13 编辑

大家好,很惭愧这是一道简单题。。。但是BST的recursion写法是我的死穴。。。 本帖里的python 2 recursion solution,我的理解是base case是root为空或者root为leaf node,closestValue(root, target)这个functon返回root node子树中的closest value。但是我不知道如何设计recursion rule,或者说我看不明白solution的L6- L10。 (如果是普通binary tree寻找closest treenode to target,我还会用recursion写:在遍历的过程中维护一个global min,并且不断与当前遍历的节点进行比较就行了; BST iterative也会写,利用BST inorder traverse结果是升序得到答案。 但是对BST recursion写法, 就不知该如何设计 。)

大家可以帮忙解答一下L6-L10的思路吗?会尽力加米,谢谢!

题目如下
[Bash shell] 纯文本查看 复制代码
Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

Given target value is a floating point.
You are guaranteed to have only one unique value in the BST that is closest to the target.
Example:

Input: root = [4,2,5,1,3], target = 3.714286

    4
   / \
  2   5
 / \
1   3

Output: 4




一个recursion的python 2 解法如下:
[Python] 纯文本查看 复制代码
def closestValue(self, root, target):
    if not root:
        return sys.maxint
    if not root.left and not root.right:
        return root.val
    node = root.right if target > root.val else root.left
    if not node:
        return root.val
    tmp = self.closestValue(node, target)
    return min((tmp, root.val), key=lambda x:abs(x-target))







评分

参与人数 1大米 +3 收起 理由
14417335 + 3

查看全部评分


上一篇:【刷题笔记】Leetcode #1143. Longest Common Subsequence
下一篇:LC 212 Trie 高赞答案解惑
我的人缘0

升级   42.43%

zea7ot 2020-8-10 13:56:35 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (669)
 
 
2% (19)    👎
本帖最后由 zea7ot 于 2020-8-10 13:59 编辑

不是大蛇选手,就着Java比划两下:
1. 既然是BST,就要挖尽它有序的特质。
中序遍历八成跑不了:有recursive和iterative两种写法。
每次砍半儿。所以时间复杂度应该是O(H)
(这道题的recursive写法并不如iterative写法好写)

2. 这个题目要求返回最小差值(variance)的树节点(node),所以在recursion里面传递二者(both)。
差值用来比较,树节点用做答案来返回。
(这两个的类型不太一样,在Java里不能简单使用一个数组来表示,需要额外处理一下)
逻辑就是:
差值初始成最大(或者跟root.val相差)。
根据相对大小砍半儿遍历,一旦发现差值比现有的差值更小的,就把这个节点记下来。
走到底(该分支的叶节点)即可返回目前记录的节点。

照顾到以上两点,应该就足够了。
这是Java的Recusive的解法 - github
这里还有Java两个iterative的解法 - github

我认为这道题应该是Medium难度。同时我也觉得:不要轻易觉得惭愧lol。
这里是一些练习树的遍历的题目列表(github),大部分都可以写成recursive和iterative两种形式。


补充内容 (2020-8-11 01:56):
以上解法只用到了二叉搜索树的左右子树/节点的大小性质,并没有使用中序遍历的单调性。
所以都算作是二分搜索-分治(Divide and Conquer)的范畴,只不过分为iterative和recursive两种写法。

补充内容 (2020-8-11 01:57):
我明天前补充使用到二叉搜索树中序遍历单调性的解法。

补充内容 (2020-8-11 03:29):
以上内容不够准确。抱歉lol!

将于明天前重新发帖总结。

评分

参与人数 2大米 +10 收起 理由
超人96825 + 2 谢谢!
14417335 + 8

查看全部评分

回复

使用道具 举报

我的人缘0

升级   3.29%

 楼主| 超人96825 2020-8-10 23:07:35 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (71)
 
 
0% (0)    👎
zea7ot 发表于 2020-8-10 13:56
不是大蛇选手,就着Java比划两下:
1. 既然是BST,就要挖尽它有序的特质。
中序遍历八成跑不了:有recurs ...

谢谢解答。我还有一些疑问,如何在recursion中利用BST的升序特性呢?

你的Java答案中,L31-L34我还是不太理解。 我隐约感觉到这几行可以缩小范围(剪枝),但是不懂为什么。为什么当node.val > target, 就对node.left进行call recursion 呢?

补充内容 (2020-8-11 01:03):
跑了几个栗子我明白了!!感觉 recursion也是在尽量缩小target在升序list中的区间,最后得到左区间和右区间和相应差值,返回最小差值。感觉的确需要多练习一下recursion写法,谢谢
回复

使用道具 举报

我的人缘0

升级   42.43%

zea7ot 2020-8-11 00:38:54 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (669)
 
 
2% (19)    👎
本帖最后由 zea7ot 于 2020-8-11 00:53 编辑

A Binary Search Tree is is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree - WIKI.
简单地讲:针对某一个数节点,如果需要找比当前节点小的节点,就去左子树找;如果需要找比当前节点大的节点,就去右子树找。
以上解法已经应用了剪枝,因为每次砍半儿,由O(N)的遍历降低为O(H)的遍历。相比较而言,如果是一个普通的二叉树(Binary Tree),节点之间不存在确定的大小关系,则需要进行O(N)的遍历。

二叉搜索树的中序遍历是从小到大有序的。这题目最"天真直率"的作法是:把BST通过中序遍历拉成排序数列,时间花费O(N)。然后使用遍历或者二分查找来找最小差值在哪里,时间花费O(N) / O(lg(N))。这样一共是O(N)的时间花费。


这道题目还可以做更多的剪枝:
当差别(variance)先变小而后变大的时候,就可以停下了。根据单调性,后面只会越来越大/远。
好吧,最后这条是成立的:因为在对半遍历的过程中,差别是会发生波动的。如果差别增大,并不能保证后面不会遇到更小。
这段我先放这里了,并没有足够的验证。等我仔细研究下再回来补充。


补充内容 (2020-8-11 01:57):
以上解法只用到了二叉搜索树的左右子树/节点的大小性质,并没有使用中序遍历的单调性。
所以都算作是二分搜索-分治(Divide and Conquer)的范畴,只不过分为iterative和recursive两种写法。

补充内容 (2020-8-11 01:57):
我明天前补充使用到二叉搜索树中序遍历单调性的解法。

补充内容 (2020-8-11 03:27):
"树"节点

错别字

补充内容 (2020-8-11 03:29):
以上内容不够准确。抱歉lol!

将于明天前重新发帖总结。

评分

参与人数 2大米 +5 收起 理由
超人96825 + 2 非常谢谢你,我明白了
14417335 + 3

查看全部评分

回复

使用道具 举报

我的人缘0

升级   3.29%

 楼主| 超人96825 2020-8-11 01:18:21 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (71)
 
 
0% (0)    👎
zea7ot 发表于 2020-8-11 00:38
A Binary Search Tree is is a rooted binary tree whose internal nodes each store  ...
非常谢谢你,我明白了
回复

使用道具 举报

我的人缘0

升级   42.43%

zea7ot 2020-8-11 03:27:05 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (669)
 
 
2% (19)    👎
zea7ot 发表于 2020-8-10 13:56
不是大蛇选手,就着Java比划两下:
1. 既然是BST,就要挖尽它有序的特质。
中序遍历八成跑不了:有recurs ...

以上内容是不够准确的。很抱歉lol

评分

参与人数 1大米 +2 收起 理由
超人96825 + 2 不会啊,谢谢; 分治说的很清楚。

查看全部评分

回复

使用道具 举报

我的人缘0

升级   25%

T大农民伯伯 2020-8-11 08:09:51 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (99)
 
 
0% (0)    👎
我的解法:
[Bash shell] 纯文本查看 复制代码
class Solution:
    def closestValue(self, root: TreeNode, target: float) -> int:
        def FindValue(node):
            if node:
                print(node.val)
                if node.val >= target:
                    if node.left:
                        return min([FindValue(node.left), node.val], key = lambda x: abs(x-target))
                    else:
                        return node.val
                else:
                    if node.right:
                        return min([FindValue(node.right), node.val], key = lambda x: abs(x-target))
                    else:
                        return node.val
        return FindValue(root)

先把这题当做普通的二叉树递归来写,再根据BST的性质来决定在每一个父节点时选择进入左边还是右边的子树。

评分

参与人数 1大米 +2 收起 理由
超人96825 + 2 只进入左子树还是右子树说的太清晰了!!

查看全部评分

回复

使用道具 举报

我的人缘0

升级   3.29%

 楼主| 超人96825 2020-8-11 09:39:20 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (71)
 
 
0% (0)    👎
zea7ot 发表于 2020-8-11 03:27
以上内容是不够准确的。很抱歉lol
不会啊,谢谢; 分治说的很清楚。
回复

使用道具 举报

我的人缘0

升级   3.29%

 楼主| 超人96825 2020-8-11 10:12:21 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (71)
 
 
0% (0)    👎
T大农民伯伯 发表于 2020-8-11 08:09
我的解法:
[mw_shl_code=bash,true]class Solution:
    def closestValue(self, r ...
只进入左子树还是右子树说的太清晰了!!
回复

使用道具 举报

我的人缘0

升级   5%

cent 2020-8-12 23:38:49 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   0% (0)
 
 
0% (0)    👎
[Python] 纯文本查看 复制代码
    def closestValue(self, root, target):
        self.min_val = float('inf')
        self.find_closest_node_val(root, target)
        return self.min_val
        
    def find_closest_node_val(self, node, target):
        if not node:
            return
        if node.val == target:
            self.min_val = node.val
            return
            
        if abs(node.val - target) < abs(self.min_val - target):
            self.min_val = node.val
        
        if node.val > target:
            self.find_closest_node_val(node.left, target)
        else:
            self.find_closest_node_val(node.right, target)
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

快速回复 返回顶部 返回列表