111qqz的小窝

老年咸鱼冲锋!

leetcode 235. Lowest Common Ancestor of a Binary Search Tree(求一个BST中某两个节点LCA)

题目链接

题意:求一个BST中某两个节点LCA….

思路:卧槽。。。竟然求LCA…直接想到的显然是Tarjan的方法或者。。。RMQ+DFS。。。但是感觉。。。leetcode怎么可能考算法。。。。于是想到。。。可以从BST下手。。。

两个节点的LCA的值一定在这两个节点之间。

可以根据这个条件做二分。。。

这道题的收获是。。。不要被已知的东西限制住思路。。。tarjan或者RMQ+DFS显然也能做。。。但是那样的相当于没有用到BST的条件。。。

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz