根据遍历结果推导二叉树结构

已知前序遍历为{1,2,4,7,3,5,6,8}，中序遍历为{4,7,2,1,5,3,8,6}，它的二叉树是怎么样的？
二叉树的前序遍历递归算法：

    public void preOrderTraverse(BiTree t) {
        if (t == null) {
            return;
        }
        System.out.print(t.val);
        preOrderTraverse(t.left);
        preOrderTraverse(t.right);
    }

二叉树的中序遍历递归算法：

    public void preOrderTraverse(BiTree t) {
        if (t == null) {
            return;
        }
        preOrderTraverse(t.left);
        System.out.print(t.val);
        preOrderTraverse(t.right);
    }

二叉树的后续遍历递归算法：

    public void preOrderTraverse(BiTree t) {
        if (t == null) {
            return;
        }
        preOrderTraverse(t.left);
        preOrderTraverse(t.right);
        System.out.print(t.val);
    }

前序遍历是先打印当前节点再递归左和右，且前序遍历的第一个节点的值为1，所以1是根节点。
再由中序遍历可知，2、4、7是1的左子树的节点，5、3、6、8是1的右子树的节点。

image.png

然后看前序{2、4、7}可知4一定是2的子节点，而7有可能是2的子节点或4的子节点。
看中序{4、7、2}可知4是2的左子节点，7不可能是2的子节点（如果是的话中序应该为{4、2、7}或{7、2、4}），所以结合前序可知7是4的子节点，且7是4的右子节点。

image.png

同理推得：

image.png

参考自：《大话数据结构》