JZ57-二叉树的下一个结点

class Solution {
    ArrayList<TreeLinkNode> list = new ArrayList<>();

    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode == null) {
            return pNode;
        }
        TreeLinkNode root = pNode;
        while (root.next != null) {
            root = root.next;
        }
        inOrder(root);

        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) == pNode && i + 1 != list.size()) {
                return i == list.size() - 1 ? null : list.get(i + 1);
            }
        }
        return null;
    }

    public void inOrder(TreeLinkNode root) {
        Stack<TreeLinkNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            if (root.left != null) {
                stack.push(root.left);
                root = root.left;
            } else { //必须加else
                TreeLinkNode temp = stack.pop();
                list.add(temp);
                if (temp.right != null) {
                    stack.push(temp.right);
                    root = temp.right;
                }
            }
        }
    }
}

/**
 *               A
 *          B        C
 *       D     E    F  G
 *           H   I
 */
class Solution2{
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        //1.有右子树，下一结点是右子树中的最左结点，例如 B，下一结点是 H
        if (pNode.right != null) {
            TreeLinkNode pRight = pNode.right;
            while (pRight.left != null) {
                pRight = pRight.left;
            }
            return pRight;
        }
        //2.无右子树，且结点是该结点父结点的左子树，则下一结点是该结点的父结点，例如 H，下一结点是 E
        if (pNode.next != null && pNode.next.left == pNode) {
            return pNode.next;
        }
        //3.无右子树，且结点是该结点父结点的右子树，则我们一直沿着父结点追朔，直到找到某个结点是其父结点的左子树，
        // 如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点。例如 I，下一结点是 A；
        // 例如 G，并没有符合情况的结点，所以 G 没有下一结点
        if (pNode.next != null) {
            TreeLinkNode pNext = pNode.next;
            while (pNext.next != null && pNext.next.right == pNext) { //B.right==E
                pNext = pNext.next;
            }
            return pNext.next;
        }
        return null;
    }
}

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

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