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

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
import java.util.*;
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        TreeLinkNode root = pNode;
        while (null != root.next) {
            root = root.next;
        }
        Stack<TreeLinkNode> stack = new Stack<>();
        Queue<TreeLinkNode> queue = new LinkedList<>();
        TreeLinkNode copyNode = pNode;
        pNode = root;
        while (null != pNode) {
            stack.push(pNode);
            pNode = pNode.left;
        }
        while (!stack.isEmpty()) {
            pNode = stack.pop();
            queue.add(pNode);
            if (null != pNode.right) {
                pNode = pNode.right;
                while (null != pNode) {
                    stack.push(pNode);
                    pNode = pNode.left;
                }
            }
        }
        while (queue.poll() != copyNode);
        pNode = null;
        if (!queue.isEmpty()) {
            pNode = queue.poll();
        }
        return pNode;
    }
}