二叉树的下一个结点

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

节点结构

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

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

思路:

如果当前节点存在右子树,则找到右子树中序遍历第一个节点返回
如果不存在右子树,则找到父节点,如果当前节点是父节点的左节点,则返回父节点,否则返回null

代码:

 public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode==null){
            return null;
        }

        //如果当前节点存在右子树,则找到右子树中序遍历第一个节点返回
        if (pNode.right!=null){
            TreeLinkNode left=pNode.right;
            while (left.left!=null){
                left=left.left;
            }
            return left;
        }
        //如果不存在右子树
        //则找到父节点,如果当前节点是父节点的左节点,则返回父节点,否则返回null
        TreeLinkNode node=pNode;

        while (node.next!=null){
            //如果该节点是父节点的左节点
            if (node==node.next.left){
                return node.next;
            }
            node=node.next;
        }

        return null;
    }