请问哪位大神帮我理解一下Inorder Successor in BST

已经挣扎了半天，还是对这个code不能理解，应该怎么使用和理解recursion呐？平时递归对我来说就像玄学，时儿做的出，时而做不出。这种进阶一点就完全不会了。怎么办？
public TreeNode successor(TreeNode root, TreeNode p) {
     if (root == null) return null;
     if (root.val <= p.val) return successor(root.right, p);
     else {
         TreeNode left = successor(root.left, p);
         return (left != null) ? left : root;
     }
}

首先楼主需要明确BST的性质（假设树存储的是键值对Key -> Value）：一般来说，左子树的Key < 其父结点的Key，右子树的Key > 其父结点的Key，所以BST的中序遍历（inorder traversal）可以得到一个sorted的数组，BST的中序遍历，从几何上来看可以看成把所有树节点投影到x轴上，所得到的有序序列即为中序遍历所得到的结果，如下面的BST所示：

第二点就是后继节点的意义：BST某结点P的successor即为一个Key大于P.key的结点，同时此节点在所有大于P的结点中又是最小的。根据上面的BST的性质，我们可以知道，对于任意给定结点P，它的successor有两种情况：

1）当前节点（current）的Key <= P.key； successor一定在P的右子树里面；

这种情况最简单，上面的例子，如果P = S，我们走到S，current = S, current.key <= P.key，那么P的successor一定在current的右子树里面，所以我们走到X，最后返回X；

这部分对应这段代码：

1. if (root.val <= p.val) return successor(root.right, p);

复制代码

2）current.key > P.key；
到这里，我们知道什么信息呢？我们知道current一定比P大，但我们不知道是不是Tree中有结点还小于current，如果有这样的结点，那么successor应该是更小的结点，而不是current；但是没有遍历到后面的结点，我们是不是知道有没有这样的结点存在，所以我们先把current保存起来，然后继续寻找current的左子树（左子树的结点都小于current，但大于P）；

还是上面的图例，如果P = R，首先我们走到S，current = S，current.key > P.key，所以先保存S，继续寻找S的左子树。然后我们来到E，E.key <= P.key，所以我们要在E的右子树里面的寻找，之后来到S，还是继续寻找S的右子树，为null，最后一级一级向上返回，如果返回值不为null，则返回之前保存的结点，最后得到S为R的successor。

这部分对应这段代码：

1.      else {
   
2.          TreeNode left = successor(root.left, p);
   
3.          return (left != null) ? left : root;
   
4.      }

复制代码

差不多应该明白啦，有什么不懂的随时追问哒~



补充内容 (2021-07-15 10:44 +8:00):
"之后来到S，还是继续寻找S的右子树"，应该是“之后来到R，还是继续寻找R的右子树”，论坛只能修改一次，不是很方便额

这个函数应该是在寻找root树里值大于节点p中最小的节点。还有应该就是assume这个root树是BST。

这不算是典型的in-order traversal。这种东西就是多练多看，就能渐渐掌握了。

BobbyBear 发表于 2021-7-12 19:01
这个函数应该是在寻找root树里值大于节点p中最小的节点。还有应该就是assume这个root树是BST。

这不算是 ...

谢谢啦，那我再多练练看

要找第一个大于p的节点，如果root.val <= p.val，那目标节点肯定在右子树，所以是recursion到root.right，如果root.val > p.val进到了else，那就说明现在的子树所有节点都大于p了，于是就开始缩小范围当前最小的，于是就一直往左走直到找到最小的非null的那个。

这道题也可以用inorder traversal来做，可能更清楚一点。。BST的inorder traversal是sorted，所以可以开始inorder traversal，然后找到第一个大于p的就行了。

dorisH 发表于 2021-7-13 18:30
要找第一个大于p的节点，如果root.val  p.val进到了else，那就说明现在的子树所有节点都大于p了，于是就开 ...

这样解释很清楚了，多谢大神

thrillerの空 发表于 2021-7-14 23:53
首先楼主需要明确BST的性质（假设树存储的是键值对Key -> Value）：一般来说，左子树的Key < 其父结点的Key ...

如果楼主对更难的二叉树算法有兴趣，这个题目推荐好好理解一下额，因为这个算法对BST也是适用的，也对“令人闻风丧胆”红黑树也是适用的额，而且递归是BST和红黑树的基本算法，理解掌握非常重要哒

Morris 算法了解一下

thrillerの空 发表于 2021-7-14 08:53
首先楼主需要明确BST的性质（假设树存储的是键值对Key -> Value）：一般来说，左子树的Key < 其父结点的Key ...

天啊，写的好详细，第一次看到这个投影图。谢谢大牛的一步步解释哪步在干嘛。我花点时间消化一下。

pnwair 发表于 2021-7-15 09:38
天啊，写的好详细，第一次看到这个投影图。谢谢大牛的一步步解释哪步在干嘛。我花点时间消化一下。

如果你想对BST有更深入的了解，比如插入，删除操作，可以看看我之前写的系列文章哦，希望对你有帮助哒：

超详细！红黑树详解文章汇总（含代码）
里面的第一章就是将BST的哦，有什么意见也可以告诉我哒