剑指offer系列之五十七：二叉树的下一个节点

题目描述

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

根据中序遍历的特点，要找到一个节点的下一个节点无非就是三种情况：1、有右子树，这时只需要把其右孩子作为下一个遍历的（并不是要找的）节点，然后沿着该节点的左子树（如果有的话）出发，直到遇到叶子节点，那么该叶子节点就是其下一个要找的节点；2、没有右子树，则判断该节点是否是其父节点的左孩子，如果是则其下一个要找的节点是其父节点；3、如果不是其父节点的左孩子，则把其父节点作为下一个遍历的节点，向上回溯，直到找到父节点没有父节点并且父节点是父节点的父节点的左孩子为止。综合这三种情况就可以找到二叉树中任意一个节点的下一个节点。下面是具体的实现代码（已被牛客AC）：

public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        TreeLinkNode curNode = null;
        //第一步：判断是否有右孩子
        if(pNode.right != null){
            curNode = pNode.right;
            while(curNode.left != null) curNode = curNode.left;
            return curNode;
        }
        //第二步：判断是否是其父节点的左孩子
        if(pNode.next == null) return null;
        if(pNode == pNode.next.left){
            return pNode.next;
        }
        //第三步：向上找其父节点，直到父节点是其父节点的父节点的左孩子
        curNode = pNode.next;
        while(curNode.next != null){
            if(curNode == curNode.next.left){
                return curNode.next;
            }
            //继续向上找父节点
            curNode = curNode.next;
        }
        return null;
    }
}