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

来晚了来晚了~
首先感谢楼主发问，所以我才能发现自己的问题。
上面的阐释有问题。我接下来要更正:
首先简单澄清一下:在接下来的阐释中，二分搜索算(Binary Search)算是分治(Divide and Conquer)的范畴。我把更详细的讨论放在本帖最后。

1. 我上述的阐释和解法只涉及到了二分搜索，并没有使用到中序遍历的单调性。
Binary Search Iterative - github
Binary Search Recursive - github
简单地来讲，是分治的思想，使用的是BST左右根三个树节点的大小关系:需要大的就去右子树，需要小的就去左子树。
但需要注意的是：按照上述原理的路径并不是单调的，差值(variance)也并不是单调的，并不是前面递减、后面一定递增的。所以，这个剪枝"一旦发现差值(variance)增大即可退出"并不成立。

2. 以下的解法使用到了中序遍历二叉搜索树的单调性。思路是:先从最小的树节点找起，然后逐次增大。相比较于上面的解法，这就具有单调性了。差别(Variance)肯定是先减小后增大，或者一直减小或者一直增大。基于此，当差异(Variance)增大的时候，就可以返回值了。这个剪枝是成立的。
Inorder Traversal Iterative - github
Inorder Traversal Recursive: github
Morris Inorder Traversal也可以解这道题目，但写起来实在太啰嗦了，这里就不推荐了。

这是上述全部的解法 - github。这是我目前总结的关于树的遍历的题目列表(github),这是关于树的题目列表(github)。
只是基于目前做过的题目，并不能涵盖所有的范围。

如果有不对的地方，还请指出。请多多指教。


关于二分搜索算不算分治的范畴，我认为是这样的：二分搜索是算法层面、而分治是技巧层面的分类，二者不在一个层面，可以共存；分治是把问题切成小问题、逐个解决后、再合并起来，典型的分治就是Merge Sort, e.g. Merge K Sorted List的O(N)解法，而二分搜索则只针对切割后的某一个(而不是全部)小问题，解决问题(即找到或者确定找不到解)即返回，是没有最后的合并操作的。

至于二分搜索算不算分治，见仁见智。如果错了，希望高人能指正并引用理论。





补充内容 (2020-8-14 06:19):
Merge K Sorted List的分治解法的时间复杂度是O(N * lg(K))，特此更正。