題目

給定一個(gè)二叉樹和其中的一個(gè)結(jié)點(diǎn)，請找出中序遍歷順序的下一個(gè)結(jié)點(diǎn)并且返回。注意，樹中的結(jié)點(diǎn)不僅包含左右子結(jié)點(diǎn)，同時(shí)包含指向父結(jié)點(diǎn)的指針。

程序核心思想

如果這個(gè)節(jié)點(diǎn)的右孩子不為空，那么它的下一個(gè)節(jié)點(diǎn)一定在它的右子樹上，所以再檢查它的右子樹，返回它右子樹的最左的節(jié)點(diǎn)（如果有的話），否則返回右子樹的根節(jié)點(diǎn)。
如果這個(gè)節(jié)點(diǎn)的右孩子為空，那么檢查它是否是它父節(jié)點(diǎn)的右節(jié)點(diǎn)，如果不是（那就是它父節(jié)點(diǎn)的左節(jié)點(diǎn)），那么返回它的父節(jié)點(diǎn)；如果是（它父節(jié)點(diǎn)的右節(jié)點(diǎn)），那么返回讓它指向它的父節(jié)點(diǎn)，再次做同樣的檢查（是否是它父節(jié)點(diǎn)的右節(jié)點(diǎn)），直到他的父節(jié)點(diǎn)為空，那么意為著題目給出的這個(gè)節(jié)點(diǎn)是整棵樹的最右的節(jié)點(diǎn)，則返回null。

Tips

在做pNode == pNode.next.right這種一個(gè)指針后面還有指針的操作時(shí)，要保證第一個(gè)不為空指針，方法可以是pNode.next != null && pNode == pNode.next.right。

代碼

/*
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)
    {
        if(pNode == null)    return null;
        
        while(true){
            if(pNode.right != null){
                pNode = pNode.right;
                while(pNode.left != null){
                    pNode = pNode.left;
                }
                return pNode;
            }else{
                while(pNode.next != null  && pNode == pNode.next.right){
                    pNode = pNode.next;
                }
                if(pNode.next == null || pNode.next == pNode){
                    return null;
                }
                return pNode.next;
            }
        }
    }
}