题目描述
思路
题目很明显是需要中序遍历，这里需要找到中序遍历中，指定节点的后继节点（中序遍历的顺序是：左根右），即，可能会存在寻找左子节点的父节点情况，这里，最简单容易想到的是双指针+中序遍历非递归，其中一个指针用来遍历，另一个指针则指向当前遍历节点的上一个节点
代码
/**
* 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) {
//创建一个栈
Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
//创建双指针
TreeNode prev = null, curr = root;
while (!stack.isEmpty() || curr != null) {
while (curr != null) {
//将所有左子节点入栈
stack.push(curr);
curr = curr.left;
}
/*跳出循环时，curr == null，说明所有左子节点遍历完毕，此时
需要出栈，获取中序遍历中的‘根’ */
curr = stack.pop();
if (prev == p) {
return curr;
}
prev = curr;
curr = curr.right;
}
return null;
}
}
