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

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 {
    TreeLinkNode last = null;
    TreeLinkNode result = null;
    TreeLinkNode goal = null;

    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        // 中序遍历 左中右,递归
        // 记录last，然后比较last.val==pNode.val
        goal = pNode;
        TreeLinkNode root = pNode;
        while(root.next != null) {
            root = root.next;
        }
        middle(root);
        return result;
    }

    void middle(TreeLinkNode pNode) {
        if(pNode == null) {
            return;
        }
        middle(pNode.left);
        if(last != null && last.val == goal.val) {
            result = pNode;
        }
        last = pNode;
        middle(pNode.right);
    }
    //     5
    //   4   #
    //  3 #
    // 2
}

首先while+next找到root，同时记录goal就是对比的目标。然后对root做中序遍历，遍历的同时，记录last，且判断last是否等于goal，如果等于，则给result设置为cur。