题目描述：给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？树中的节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针。
思路：
- 若一个节点有右子树，那么它的下一个节点就是它的右子树中的最左子节点。
- 若一个节点没有右子树，则向上不断遍历找第一个左子树中包含该节点的的节点
代码实现：
/**
* 题目类型：二叉树
*
* 题目要求：给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？
* 树中的节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针
*
* 思路：1. 若一个节点有右子树，那么它的下一个节点就是它的右子树中的最左子节点。
* 2. 若一个节点没有右子树，则向上不断遍历找第一个左子树中包含该节点的的节点
*/
public class GetNextNode {
/**
* 节点类
*/
public static class TreeLinkNode {
int value;
TreeLinkNode left;
TreeLinkNode right;
TreeLinkNode next;
TreeLinkNode(int val) {
this.value = val;
}
}
/**
* 找出中序遍历序列的下一个节点
*
* @param pNode 给定的节点
* @return 返回给定节点的下一节点
*/
private static TreeLinkNode getNext(TreeLinkNode pNode) {
if (pNode == null)
return null;
if (pNode.right != null) { // 右子树不为空
TreeLinkNode pRight = pNode.right;
while (pRight.left != null) {
pRight = pRight.left; // 下一节点为右子树的最左子节点
}
return pRight;
// 右子树为空
} else {
while (pNode.next != null) {
TreeLinkNode parent = pNode.next;
if (parent.left == pNode) {
System.out.print("下一节点为：" + parent.value);
return parent;
}
pNode = pNode.next;
}
}
return null;
}
}
