给定一棵二叉树和其中的一个结点，找出中序遍历序列的下一个节点。（树中的节点有指向左右子节点和父节点指针）。

二叉树节点类

public class TreeNode {
    private int item;
    private TreeNode left;
    private TreeNode right;
    private TreeNode parent;

    public TreeNode(int item) {
        this.item = item;
    }

    //getter和setter
}

根据前序序列构建带有父节点的二叉树

     /**
     * 根据前序遍历构建带有父节点指针的二叉树
     * @param linkedList 前序遍历链表
     * @param parent 父节点
     * @return 返回二叉树
     */
    private static TreeNode createTree(LinkedList<Integer> linkedList,TreeNode parent){
        if (linkedList == null || linkedList.isEmpty()){
            return null;
        }
        //前序遍历的首元素即为子树的根节点
        Integer item = linkedList.removeFirst();
        TreeNode node = null;
        if (item != null){
            node = new TreeNode(item);
            node.setParent(parent);
            node.setLeft(createTree(linkedList,node));
            node.setRight(createTree(linkedList,node));
        }
        return node;
    }

二叉树的下一个节点

    /**
     * 根据某一个结点，获取中序遍历的下一个节点
     * @param node 某一个节点
     * @return 返回下一个节点
     */
    private static TreeNode getNextItem(TreeNode node){
        //右子树存在，下一个节点为右子树的最左节点
        if (node.getRight() != null){
            TreeNode left = node.getRight();
            while (left.getLeft() != null){
                left = left.getLeft();
            }
            return left;
        }

        TreeNode parent = node.getParent();
        //右子树为空，且该节点为左节点，则下一个节点为该节点的父节点
        if (parent.getLeft() == node && node.getRight()==null) {
            return parent;
        }
        //右子树为空，且该节点为右结点，遍历父节点，直到找到某一节点为左节点，则该左节点的父节点为下一个节点。
        // 若找不到此节点，则说明当前节点在中序遍历中为最后一个元素，下一个节点为空
        if (parent.getRight() == node && node.getRight() == null){
            while (parent.getParent() != null){
                if (parent.getParent().getLeft() == parent){
                    return parent.getParent();
                }
                parent = parent.getParent();
            }
            //当前节点在中序遍历中为最后一个元素，下一个节点为空
            return new TreeNode(-1);
        }
        return new TreeNode(-1);
    }

中序遍历

    /**
     * 中序遍历
     * @param node
     */
    private static void inOrderTraveral(TreeNode node){
        if (node == null){
            return;
        }
        inOrderTraveral(node.getLeft());
        System.out.print(node.getItem() + " ");
        inOrderTraveral(node.getRight());
    }

测试

    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>(
                Arrays.asList(new Integer[]{3,2,9,null,null,10,null,null,8,null,4}));
        TreeNode node = createTree(list,null);
        System.out.println("中序遍历：");
        inOrderTraveral(node);
        System.out.println();
        TreeNode testNode = node.getLeft().getRight();
        System.out.println("给定的节点值："+testNode.getItem());
        System.out.println("下一个节点值："+getNextItem(testNode).getItem());
    }

结果

中序遍历：
9 2 10 3 8 4 
给定的节点值：10
下一个节点值：3