题解 | #二叉树的下一个结点#

一定要手画一个二叉树 然后分析其子节点和父节点形态的可能性， 最后求出在不同形态下，下一个节点的位置

/*
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 temp;
        if(pNode.right != null){
            temp = pNode.right;
            while(temp.left != null){
                temp = temp.left;
            }
            return temp;
        }
        
        // 没有右子树，父节点也不存在，则返回null
        if(pNode.next == null){
            return null;
        }
        
        // 如果不存在右子树，但是给定节点是其父节点的左子树。下一个节点为其父节点
        if(pNode == pNode.next.left){
            return pNode.next;
        }
        
        
        // 如果不存在右子树，但是给定节点是其父节点的右子树。
        // 那么就得顺着父节点一直向上寻找，直到找到一个节点是其父节点的左子树，那么这个节点的父节点就是要寻找的节点
        if(pNode == pNode.next.right){
            temp = pNode.next;
            while(temp != null && temp.next != null){
                if(temp == temp.next.left){
                    return temp.next;
                }else{
                    temp = temp.next;
                }
            }
            return null;
        }
        
        // unreachable
        return null;

    }
}