二叉树的下一个节点_JAVA_中等

• 寻找该节点中序遍历的下一个节点，有可能在它父辈，也可能在他孩子
• 如果该节点右孩子为空，则下一个节点为父辈，那么找到了该节点所属于的第一个左支系的父辈，则是所求节点
• 如果该节点右孩子不为空，则下一个节点为它的右孩子的第一个左孩子或者是它的右孩子

import java.util.*;
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if(pNode == null) {
            return null;
        }

        // 没有右孩子则找父节点
        if(pNode.right == null) {
            TreeLinkNode father = pNode.next;
            // 找出该孩子属于父辈的第一个非右支系
            while(father != null && father.right == pNode) {
                pNode = father;
                father = father.next;
            }
            return father;
        }

        // 自己有右孩子则下一个节点为右孩子中序输出的第一个
        pNode = pNode.right;

        // 先输出左孩子
        while(pNode.left != null) {
            pNode = pNode.left;
        }

        return pNode;
    }
}