题目
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路
中序遍历特点：左中右；
- 假设该节点有右孩子，则找到右孩子的最左；
- 假设该节点没有右孩子，则应该找到父节点
- 如果该节点是父节点的左孩子，则就是父节点
- 如果该节点是父节点的右孩子，则是root节点
代码
public TreeLinkNode GetNext(TreeLinkNode pNode) {
if (pNode == null ) {
return null;
}
//判断是否有右子树,如果有右子树,则返回该右子树最左的孩子
if (pNode.right != null) {
TreeLinkNode cur = pNode.right;
while (cur.left != null) {
cur = cur.left;
}
return cur;
}
//如果没有右子树
while (pNode.next != null) {
if (pNode.next.left == pNode) {
return pNode.next;
}
pNode = pNode.next;
}
return null;
}
