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

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 {
    ArrayList<TreeLinkNode> list  = new ArrayList<>();
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        //先找根节点
        TreeLinkNode root = pNode;
        while (root.next != null) {
            root = root.next;
        }
        //进行中序遍历
        reverse(root);
        
        if(1 == list.size()) return null;
        //size要减一，避免出现目标节点为中序遍历最后一位，也就是根节点没有右子树，此时并没有满足题目的结果
        for (int i = 0; i < list.size()-1; i++) {
            if (list.get(i) == pNode) return list.get(i + 1);
        }
        return null;
    }

    void reverse(TreeLinkNode pNode) {
        if (pNode == null) return ;
        reverse(pNode.left);
        list.add(pNode);
        reverse(pNode.right);
    }
}

思路：

1. 先找到根节点
2. 根据根节点进行中序遍历，可用容器记录中序遍历的元素
3. 在容器中迭代找到和target节点相同的节点，此时下一个节点就是答案。

ps.遍历容器要注意，看上面注释