《剑指offer》面试题8：二叉树的下一个节点
题目：给定一颗二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点，树中的节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针。
思路：中序遍历是左、根、右的遍历顺序。
1、如果当前节点有右子树，则下一个节点为右子树的最左子节点。
2、如果当前节点没有右子树，(a)当前节点是父节点的左子节点，则下一个节点就是父节点。（b）当前节点是父节点的右子节点，则沿着执行父节点的指针向上遍历，直到找到一个节点是它父节点的左子节点，则该节点的父节点是下一个节点。如果没找到，则没有下一个节点（已经是最后一个节点）。
代码如下：
public TreeNode getNext(TreeNode node) {
if (node == null) {
return null;
}
if (node.right != null) {
TreeNode rightNode = node.right;
while (rightNode.left != null) {
rightNode = rightNode.left;
}
return rightNode;
}
while (node.parent != null) {
if (node.parent.left == node) {
return node.parent;
}
node = node.parent;
}
return null;
}
