算法006

描述

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

例子

Input:
	二叉树
Output:
	中序遍历顺序的下一个结点

思路

中序遍历顺序的下一个结点，中序遍历是左根右， 判断该结点是否有右孩子，

1. 若有，则下一个结点的最左子结点
2. 若无，则下一个结点为第一个左链指向该结点的祖先结点的结点

代码

public class Question006 {

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

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

    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        TreeLinkNode resultNode = null;
        if(null != pNode.right) {
            resultNode = pNode.right;
            while (null != resultNode.left) {
                resultNode = resultNode.next;
            }
        } else {
            TreeLinkNode temp = pNode;
            resultNode = pNode.next;
            while (null != resultNode && resultNode.left != temp) {
                temp = pNode.next;
                resultNode = temp.next;
            }
        }
        return resultNode;
    }
}