/*
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 root) {
        if (root == null) {
            return null;
        }
        TreeLinkNode cur = root;
        // 如果当前节点有右子树
        // 那么答案就是右子树中最左边的节点
        if (cur.right != null) {
            cur = cur.right;
            while (cur.left != null) {
                cur = cur.left;
            }
            return cur;
        }
        // 当前节点没有右子树
        // 判断当前节点是其父节点的左子树还是右子树
        while (cur.next != null) {
            TreeLinkNode parent = cur.next;
            // 如果当前节点是其父节点的左子树，那么答案就是父节点
            if (parent.left == cur) {
                return parent;
            }
            // 如果当前节点是其父节点的右子树，继续向上回溯
            cur = parent;
        }
        return null;
    }
}