目录

 一、题目

1、题目描述

2、基础框架

3、原题链接

二、解题报告

1、思路分析

（1）中序遍历求解

（2）用二叉搜索树的性质求解

2、代码详解

  （1）中序遍历

 （2）利用二叉搜索树的性质

三、本题小知识

 一、题目

1、题目描述

设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。

如果指定节点没有对应的“下一个”节点，则返回null。

示例 1：

输入: root = [2,1,3], p = 1  2 / \1   3输出: 2

示例 2：

输入: root = [5,3,6,2,4,null,null,1], p = 6

      5
     / \
    3   6
   / \
  2   4
 /   
1

输出: null

2、基础框架

   Java 版本给出的基础框架代码如下：   

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {    }}

3、原题链接

    LeetCode 面试题 04.06. 后继者

二、解题报告

1、思路分析

（1）中序遍历求解

       记录当前节点，和他的上一个结点

       若当前节点的上一个结点和p结点相同则返回当前结点

       若没有结点的上一个结点和当前结点相同，则返回null

（2）用二叉搜索树的性质求解

      根据二叉搜索树的性质，我们知道中序遍历满足：

• 后继节点的节点值大于 ppp 的节点值；

• 后继节点是节点值大于 ppp 的节点值的所有节点中节点值最小的一个节点。

2、代码详解

  （1）中序遍历

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { //定义栈结构来实现部分中序遍历 LinkedList stack=new LinkedList(); //pre记录当前结点的前一个结点 TreeNode pre=null; //记录当前结点  中序遍历 左->根->右 TreeNode cur=root; while(!stack.isEmpty()||cur!=null){     while(cur!=null){//cur结点入栈  stack.addFirst(cur);  cur=cur.left;}     //抛出栈顶结点     cur=stack.poll();     //r如果前一个结点为p则返回当前结点     if(pre==p){  return cur;     }     //更新前一个结点     pre=cur;     //检验右子树     cur=cur.right; } return null;    }}

 （2）利用二叉搜索树的性质

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { TreeNode successor = null; TreeNode node = root; while (node != null) {     //当前结点比p结点的值大，把结果结点更新为当前节点     //并在继续检测左子树     if (node.val > p.val) {  successor = node;  node = node.left;     } else {  //当前结点小于p结点，在右子树中找  node = node.right;     } } return successor;    }}

三、本题小知识

二叉搜索树  左子树所有结点比根结点小，右子树所有结点比根结点大