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

思路是：分两大类节点：有右节点和无右节点 有右节点：直接找右节点的最高（最底层）且最左的节点，就是该节点。 没有右节点：先判断是否是根节点，是根节点则返回null（因为没有右节点了），不是根节点判断是左节点还是右节点。是左节点：直接返回父节点（因为没有右节点），是右节点返回拐角处节点的父节点（用两个指针判断拐角点）。

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.right != null){
            TreeLinkNode tmp = pNode.right;
            
            while(tmp.left != null){
                tmp = tmp.left;
            }
            return tmp;
        }
        //不存在右节点
        else{
            //根节点
            if(pNode.next == null){
                return null;
            }else{//不是根节点
                if(pNode.next.left == pNode){
                    return pNode.next;
                }else{
                    //右节点关键代码（用两个指针判断拐弯）
                    TreeLinkNode tmp = pNode;
                    TreeLinkNode root = pNode;
                    while(root.next != null){
                        root = tmp.next;
                        if(root.left == tmp){
                            return root;
                        }
                        tmp = root;
                    }
                }
            }
        }
        return null;
    }
}