二叉树的下一个结点

题目：

给定一个二叉树和其中一个结点，如何找出中序遍历的下一个结点？树中的节点除了两个分别指向左、右子节点的指针外，还有一个指向父节点的指针。

解答：

 1 public class Solution {
 2 
 3     public TreeLinkNode GetNext(TreeLinkNode pNode) {
 4         if(pNode == null) {
 5             return null;
 6         }
 7 
 8         TreeLinkNode pNext = null;
 9         if(pNode.right != null) {
10 
11             TreeLinkNode pRight = pNode.right;
12             while(pRight.left != null) {
13                 pRight = pRight.left;
14             }
15 
16             pNext = pRight;
17         } else if(pNode.next != null) {
18             TreeLinkNode pCurrent = pNode;
19             TreeLinkNode pParent = pNode.next;
20             while(pParent != null && pParent.right == pCurrent) {
21                 pCurrent = pParent;
22                 pParent = pParent.next;
23             }
24 
25             pNext = pParent;
26         }
27 
28         return pNext;
29     }
30 }