美文网首页
《剑指offer第二版》面试题7:重建二叉树(java)

《剑指offer第二版》面试题7:重建二叉树(java)

作者: castlet | 来源:发表于2020-03-05 23:10 被阅读0次

    题目描述

    输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果都不包含重复数字。例如,输入前序遍历序列{1,2,4,7,3,5,6,8} 和中序遍历序列{4,7,2,1,5,3,8,6},则重建的二叉树为:

              1
            /   \
           2     3
          /     / \
         4     5   6
          \       /
           7     8
    

    解题思路:

    1. 以前序遍历序列A:{1,2,4,7,3,5,6,8} 和中序遍历序列B:{4,7,2,1,5,3,8,6} 为例。
    2. 前序遍历的第一个数字"1"为树的根节点。
    3. "1"将中序遍历的序列分为两部分,B1:{4,7,2}和B2:{5,3,8,6}。B1为根节点左子树的所有节点。B2为根节点右子树的所有节点。
    4. 因为左子树有三个节点(B1的数量),所以左子树的前序遍历为A1:{2,4,7}。同理右子树的前序遍历为A2:{3,5,6,8}。
    5. 此时问题转化为从A1和B1恢复左子树,从A2和B2中恢复右子树。
    6. 递归处理即可。

    代码

    TreeNode construtTree(int[] preOrder, int[] inOrder) {
        if (preOrder == null || inOrder == null) {
            return null;
        }
        if (preOrder.length != inOrder.length) {
            return null;
        }
        return rConstrutTree(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length - 1);
    }
    
    /**
     * @param preOrder 前序遍历数组
     * @param preS     前序遍历数组的开头index
     * @param preE     前序遍历数组的末尾index
     * @param inOrder  中序遍历数组
     * @param inS      中序遍历数组的开头index
     * @param inE      中序遍历数组的末尾index
     * @return         返回当前序列根节点
     */
    TreeNode rConstrutTree(int[] preOrder, int preS, int preE, int[] inOrder, int inS, int inE){
        if (preS > preE || inS > inE) {
            return null;
        }
        TreeNode root = new TreeNode(preOrder[preS]);
        int i = inS;
        while (inOrder[i] != preOrder[preS]) {
            i ++;
        }
        int nodeCount = i - inS; // 左子树的节点数量
        // 递归重建左子树
        root.left = rConstrutTree(preOrder, preS + 1, preS + nodeCount, inOrder, inS, inS + nodeCount - 1);
        // 递归重建右子树
        root.right = rConstrutTree(preOrder, preS + nodeCount + 1, preE, inOrder, inS + nodeCount + 1, inE);
        return root;
    }
    

    相关文章

      网友评论

          本文标题:《剑指offer第二版》面试题7:重建二叉树(java)

          本文链接:https://www.haomeiwen.com/subject/aserrhtx.html