加米lc 270, 求问closest binary search tree value思路

大家好，很惭愧这是一道简单题。。。但是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的思路吗？会尽力加米，谢谢！

题目如下

1. Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.
   
2. 
   
3. Note:
   
4. 
   
5. Given target value is a floating point.
   
6. You are guaranteed to have only one unique value in the BST that is closest to the target.
   
7. Example:
   
8. 
   
9. Input: root = [4,2,5,1,3], target = 3.714286
   
10. 
    
11.     4
    
12.    / \
    
13.   2   5
    
14. / \
    
15. 1   3
    
16. 
    
17. Output: 4

复制代码

一个recursion的python 2 解法如下：

1. def closestValue(self, root, target):
   
2.     if not root:
   
3.         return sys.maxint
   
4.     if not root.left and not root.right:
   
5.         return root.val
   
6.     node = root.right if target > root.val else root.left
   
7.     if not node:
   
8.         return root.val
   
9.     tmp = self.closestValue(node, target)
   
10.     return min((tmp, root.val), key=lambda x:abs(x-target))

复制代码

不是大蛇选手，就着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!

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

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写法，谢谢

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!

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

zea7ot 发表于 2020-8-11 00:38
A Binary Search Tree is is a rooted binary tree whose internal nodes each store  ...

非常谢谢你，我明白了

zea7ot 发表于 2020-8-10 13:56
不是大蛇选手，就着Java比划两下：
1. 既然是BST，就要挖尽它有序的特质。
中序遍历八成跑不了：有recurs ...

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

我的解法：

1. class Solution:
   
2.     def closestValue(self, root: TreeNode, target: float) -> int:
   
3.         def FindValue(node):
   
4.             if node:
   
5.                 print(node.val)
   
6.                 if node.val >= target:
   
7.                     if node.left:
   
8.                         return min([FindValue(node.left), node.val], key = lambda x: abs(x-target))
   
9.                     else:
   
10.                         return node.val
    
11.                 else:
    
12.                     if node.right:
    
13.                         return min([FindValue(node.right), node.val], key = lambda x: abs(x-target))
    
14.                     else:
    
15.                         return node.val
    
16.         return FindValue(root)

复制代码

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

zea7ot 发表于 2020-8-11 03:27
以上内容是不够准确的。很抱歉lol

不会啊，谢谢； 分治说的很清楚。

T大农民伯伯 发表于 2020-8-11 08:09
我的解法：
[mw_shl_code=bash,true]class Solution:
    def closestValue(self, r ...

只进入左子树还是右子树说的太清晰了！！

1.     def closestValue(self, root, target):
   
2.         self.min_val = float('inf')
   
3.         self.find_closest_node_val(root, target)
   
4.         return self.min_val
   
5.         
   
6.     def find_closest_node_val(self, node, target):
   
7.         if not node:
   
8.             return
   
9.         if node.val == target:
   
10.             self.min_val = node.val
    
11.             return
    
12.             
    
13.         if abs(node.val - target) < abs(self.min_val - target):
    
14.             self.min_val = node.val
    
15.         
    
16.         if node.val > target:
    
17.             self.find_closest_node_val(node.left, target)
    
18.         else:
    
19.             self.find_closest_node_val(node.right, target)

复制代码