剑指Offer-二叉树的下一个节点

二叉树的下一个节点

题目

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

思路

![](https://i.imgur.com/xUJ1nph.png)
结合图，我们可发现分成两大类：1、有右子树的，那么
下个结点就是右子树最左边的点；（eg：D，B，E，A，C，G） 2、没有右子树的，
也可以分成两类，a)是父节点左孩子（eg：N，I，L） ，那么父节点就是下一个节点 ； b)是
父节点的右孩子（eg：H，J，K，M）找他的父节点的父节点的父节点...直到当前结点是其父节
点的左孩子位置。如果没有eg：M，那么他就是尾节点。

代码

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

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

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

        TreeLinkNode target = null;
        if (pNode.right!=null){
            target = pNode.right;
            while (target.left!=null){
                target = target.left;
            }
        }else if (pNode.next !=null){
            target = pNode.next;
            TreeLinkNode cur = pNode;
            while (target!=null && target.left!=cur){
                cur = target;
                target = target.next;
            }
            return target;
        }

        return null;
    }

    public TreeLinkNode GetNext_ii(TreeLinkNode PNode){
            if (PNode == null){
                return null;
            }

            if (PNode.right!=null){
                PNode = PNode.right;
                while (PNode.left!=null) PNode = PNode.left;//如果有右子树，则找右子树的最左的节点
                return PNode;
            }

            while (PNode.next!=null){
                if (PNode.next.left==PNode) return PNode.next;//没有右子树的话就找d当前第一个父节点的左节点
                PNode = PNode.next;
            }

            return null;
    }
}