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

这大概是最笨的方法了，一个情况一个情况判断。 中序遍历：左根右

1. 若为左叶子，直接返回根结点pNode.next即可;
2. 若存在右子树： (1).其父节点为左子树 - 其本身为右叶子，返回父节点的父节点（左子树遍历结束，该到根） - 其本身为右子树，返回其右子树的左叶子，没有就返回右子树（其为根，则首先遍历它的左子树） (2).其沿路父结点中存在为左子树的情况（还有未遍历的右子树） - 其本身为右叶子，返回root结点 - 其本身为右子树，返回其右子树的左叶子，没有就返回右子树
3. 若其为root的右子树的尾部的右叶子，则返回null
4. 若为root且没有右子树，返回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 == null)
            return null;
        if (pNode.right == null && pNode.next == null) // 若为root且没有右子树
            return null;
        if (pNode.right != null) { // root结点的下一个结点
            if (pNode.right.left != null) {
                pNode = pNode.right;
                while (pNode.left != null)
                    pNode = pNode.left;
                return pNode;
            }
            else
                return pNode.right;
        }
        else if (pNode == pNode.next.right) { // 若为右子树
            TreeLinkNode temp = new TreeLinkNode(-1);
            temp = pNode.next;
            if (temp == temp.next.left)//其根结点为左子树
                return temp.next;
            else {
                while (temp.next != null)
                    temp = temp.next; // 到达root结点
                TreeLinkNode leaf = new TreeLinkNode(-1);
                if (temp.right != null) { //若为root左子树中最右的叶子
                    leaf = temp.right;
                    while (leaf.right != null || leaf.left != null) {
                        if (leaf.right != null)
                            leaf = leaf.right;
                        if (leaf.left != null)
                            leaf = leaf.left;
                    }
                    if (leaf.equals(pNode)) //二叉树最底层最右的叶子
                        return null;
                }
            }
            return temp;
        }
        else 
            return pNode.next; // 若为左子树
    }
}