剑指offer 面试题6—重建二叉树-阿里云开发者社区

开发者社区> 云计算> 正文

剑指offer 面试题6—重建二叉树

简介: 题目描述: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并输出它的后序遍历序列。 分析: 前序遍历的第一个节点时根,在中序中找到这个根节点,然后左边就是左子树,右边就是右子树,这样就可

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

这里写图片描述

分析:

前序遍历的第一个节点时根,在中序中找到这个根节点,然后左边就是左子树,右边就是右子树,这样就可以递归。

用数组来记录,然后每次还重新弄数组,把左子树复制过来,右子树复制过来,递归。

public TreeNode constructionOfTree(int[] pre, int[] in) {
        if (pre == null || pre.length == 0 || in == null || in.length == 0) {
            return null;
        }

        if (pre.length == 1 && in.length == 1) {
            return new TreeNode(pre[0]);
        }

        int len = pre.length;
        int root = pre[0];
        TreeNode tree = new TreeNode(root);

        int del = -1;
        for (int i = 0; i < in.length; i++) {
            if (in[i] == root) {
                del = i;
                break;
            }
        }

        int right_length = in.length - del - 1;
        int[] left_pre = new int[del];
        int[] left_in = new int[del];
        int[] right_pre = new int[right_length];
        int[] right_in = new int[right_length];

        for (int i = 1; i < del + 1; i++) {
            left_pre[i - 1] = pre[i];
            left_in[i - 1] = in[i - 1];
        }

        for (int i = del + 1; i < pre.length; i++) {
            right_pre[i - del - 1] = pre[i];
            right_in[i - del - 1] = in[i];
        }

        tree.left = constructionOfTree(left_pre, left_in);
        tree.right = constructionOfTree(right_pre, right_in);

        return tree;
    }

下面这种我觉得好些,用记录长度的方式,不用重复建立数组。

/**  
     *   
     * @param preOrder 前序遍历数组  
     * @param inOrder 中序遍历数组  
     * @param length 数组长度  
     * @return 根结点  
     */  
    public static BinaryTreeNode Construct(int[] preOrder, int[] inOrder,int length){  
        if (preOrder == null || inOrder == null || length <= 0) {  
            return null;  
        }  
        try {  
            return ConstructCore(preOrder, 0, preOrder.length - 1, inOrder, 0,inOrder.length - 1);  
        } catch (InvalidPutException e) {  
            e.printStackTrace();  
            return null;  
        }  
    }  

    /**  
     *   
     * @param PreOrder  
     *            前序遍历序列  
     * @param startPreIndex  
     *            前序序列开始位置  
     * @param endPreIndex  
     *            前序序列结束位置  
     * @param InOrder  
     *            中序遍历序列  
     * @param startInIndex  
     *            中序序列开始位置  
     * @param endInIndex  
     *            中序序列结束位置  
     * @return 根结点  
     * @throws InvalidPutException  
     */  
    public static BinaryTreeNode ConstructCore(int[] preOrder,int startPreIndex, int endPreIndex,   
            int[] inOrder,int startInIndex, int endInIndex) throws InvalidPutException {  

        int rootValue = preOrder[startPreIndex];  
        System.out.println("rootValue = " + rootValue);  
        BinaryTreeNode root = new BinaryTreeNode(rootValue);  

        // 只有一个元素  
        if (startPreIndex == endPreIndex) {  
            if (startInIndex == endInIndex  
                    && preOrder[startPreIndex] == inOrder[startInIndex]) {  
                System.out.println("only one element");  
                return root;  
            } else {  
                throw new InvalidPutException();  
            }  
        }  

        // 在中序遍历中找到根结点的索引  
        int rootInIndex = startInIndex;  

        while (rootInIndex <= endInIndex && inOrder[rootInIndex] != rootValue) {  
            ++rootInIndex;  
        }  

        if (rootInIndex == endInIndex && inOrder[rootInIndex] != rootValue) {  
            throw new InvalidPutException();  

        }  

        int leftLength = rootInIndex - startInIndex;  

        int leftPreOrderEndIndex = startPreIndex + leftLength;  

        if (leftLength > 0) {  
            // 构建左子树  
            root.leftNode = ConstructCore(preOrder, startPreIndex + 1,  
                    leftPreOrderEndIndex, inOrder, startInIndex,  
                    rootInIndex - 1);  
        }  

        if (leftLength < endPreIndex - startPreIndex) {  
            // 右子树有元素,构建右子树  
            root.rightNode = ConstructCore(preOrder, leftPreOrderEndIndex + 1,  
                    endPreIndex, inOrder, rootInIndex + 1, endInIndex);  
        }  
        return root;  
    }  

    static class InvalidPutException extends Exception {  

        private static final long serialVersionUID = 1L;  

    }  

    public static void printPreOrder(BinaryTreeNode root) {  
        if (root == null) {  
            return;  
        } else {  
            System.out.print(root.value + " ");  
        }  

        if (root.leftNode != null) {  
            printPreOrder(root.leftNode);  
        }  

        if (root.rightNode != null) {  
            printPreOrder(root.rightNode);  
        }  
    }  

    public static void main(String[] args) throws Exception{  
        ConstructionOfTree test=new ConstructionOfTree();  
        int[] preOrder={1,2,4,7,3,5,6,8};  
        int[] inOrder={4,7,2,1,5,3,8,6};  
        printPreOrder(test.Construct(preOrder, inOrder, preOrder.length));  
    }  

BinaryTreeNode.java

public class BinaryTreeNode {
    public int value;
    public BinaryTreeNode leftNode;
    public BinaryTreeNode rightNode;

    public BinaryTreeNode() {

    }

    public BinaryTreeNode(int value) {
        this.value = value;
        this.leftNode = null;
        this.rightNode = null;
    }
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

其他文章