二叉树的下一个结点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针

解题思路

中序遍历的顺序是先左子结点（左子树），再自己，最后才是右子结点（右子树），现在题目的要求是给定一个二叉树中的某一结点，求其在中序遍历顺序的下一个结点，因此根据中序遍历的性质我们不难推断：

• 目标结点有右子树，那么它的下一个结点就是右子树最左边的结点
• 目标结点没有右子树，也可以分成两类：
  • 目标结点是其父结点左孩子，那么父节点就是下一个结点
  • 目标结点是其父结点右孩子，找它的父结点的父结点的父结点，直到当前结点是其父结点的左孩子位置。如果没找到，说明当前结点已经是尾结点

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if(pNode == null) {
            return null;
        }
        // 如果有右子树，则找右子树的最左节点
        if(pNode.right != null) {
            pNode = pNode.right;
            while(pNode.left != null) {
                pNode = pNode.left;
            }
            return pNode;
        }
        // 没右子树，则找第一个当前节点是父节点左孩子的节点
        while(pNode.next != null) {
            if(pNode.next.left == pNode) {
                return pNode.next;
            }
            pNode = pNode.next;
        }
        // 到了根节点仍没找到，则返回 null
        return null;
    }
}