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

import java.util.*;
/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    int val;
    TreeLinkNode node = null;

    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        // 保留当前节点的数值
        val = pNode.val;
        // 找到整棵树的根节点
        while (pNode.next != null)  pNode = pNode.next;

        traverse(pNode);
        return node;
    }

    // In-order Traversal模板
    private void traverse(TreeLinkNode pNode) {
        // Base case: 到叶子节点以下就返回
        if (pNode == null)  return;

        traverse(pNode.left);
        // 如果已经遍历过最开始传入的子树根节点，那此时便是它的下一位节点，直接保留当前node，
        // 并再次修改val以防止重复遍历
        if (val == Integer.MAX_VALUE)  {
            val = Integer.MIN_VALUE;
            node = pNode;
        }
        // 如果当前节点正是传入的子树根节点，修改val
        if (pNode.val == val) {
            val = Integer.MAX_VALUE;
        } 
        traverse(pNode.right);
    }
}