1、题目描述

2、解题思路

  顺序后继就是中序遍历的下一个节点。

  1、如果节点 p 有右子树，那么，p 的顺序后继就在右子树的最左侧。

  2、如果节点 p 没有右子树，那么 p 的顺序后继在它的祖宗节点当中，需要从根节点进行先序遍历，记录上一个节点。

  当遍历到某一个节点时，它的上一个节点就是 p，那么当前节点就是 p 的后继节点。

3、解题代码

/*** 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 index = p;if (index.right != null) {index = index.right;while (index.left != null) {index = index.left;}return index;}int inorder = Integer.MIN_VALUE;Stack<TreeNode> stack = new Stack<>();// 不存在右子节点，则目标在祖宗节点当中while (!stack.isEmpty() || root != null) {// 1. go left till you canwhile (root != null) {stack.push(root);root = root.left;}// 2. all logic around the noderoot = stack.pop();// if the previous node was equal to p// then the current node is its successorif (inorder == p.val) return root;inorder = root.val;// 3. go one step rightroot = root.right;}return null;}
}