题目

题目来源：力扣（LeetCode）

给定一棵二叉搜索树和其中的一个节点 p ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。

节点 p 的后继是值比 p.val 大的节点中键值最小的节点，即按中序遍历的顺序节点 p 的下一个节点。

示例 1：
image.png
输入：root = [2,1,3], p = 1
输出：2
解释：这里 1 的中序后继是 2。请注意 p 和返回值都应是 TreeNode 类型。

示例 2：
image.png
输入：root = [5,3,6,2,4,null,null,1], p = 6
输出：null
解释：因为给出的节点没有中序后继，所以答案就返回 null 了。

思路分析

二叉搜索树的中序遍历结果是一个升序序列，节点p 的中序后继，就是升序序列中节点p 的下一个元素。因此我们可以使用中序遍历来寻找节点p 的中序后继。

在中序遍历的过程中，使用变量 pre 来记录中序遍历的前一个节点，使用变量 ans 来记录节点p 的中序后继。如果当前中序遍历的前一个节点等于 p节点，那么当前遍历的节点就是要找的后继节点。

代码

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val) {
  4.  *     this.val = val;
  5.  *     this.left = this.right = null;
  6.  * }
  7.  */
  8. /**
  9.  * @param {TreeNode} root
  10.  * @param {TreeNode} p
  11.  * @return {TreeNode}
  12.  */
  14. var inorderSuccessor = function (root, p) {
  15.   let pre = null; // 记录中序遍历的前一个节点，用于与 p节点比较
  16.   let ans = null; // 记录节点p 的中序后继
  17.   // let pre = ans = null;// 先赋值为空地址
  18.   inorder(root, p);
  19.   return ans;
  21.   function inorder(root, p) {
  22.   if (root == null) return false;
  23.   // 遍历左子树 在左子树中寻找后继节点
  24.   if (inorder(root.left, p)) return true;
  25.   // 如果当前中序遍历的前一个节点等于p节点，那么当前遍历的节点就是要找的后继节点
  26.   if (pre == p) {
  27.     ans = root;
  28.     return true;
  29.   }
  30.   // 将当前遍历的节点记录起来，在遍历下一个节点时，当前节点变为前一个节点，与 p节点做比较
  31.   pre = root;
  32.   // 遍历右子树 在右子树中寻找后继节点
  33.   if (inorder(root.right, p)) return true;
  35.   return false;
  36. };
  37. };