剑指Offer:重建二叉树

题目描述

根据二叉树的前序遍历和中序遍历的结果,重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

preorder = [3,9,20,15,7]
inorder =  [9,3,15,20,7]

解题思路

前序遍历的第一个值为根节点的值,使用这个值将中序遍历结果分成两部分,左部分为树的左子树中序遍历结果,右部分为树的右子树中序遍历的结果。

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: Geekerstar
 * @Date: 2018/8/28 20:12
 * @Description: 前序遍历的第一个值为根节点的值,使用这个值将中序遍历结果分成两部分,左部分为树的左子树中序遍历结果,右部分为树的右子树中序遍历的结果。
 */
public class Solution {
    //缓存中序遍历数组每个值对应的索引
    private Map indexForInOrders = new HashMap<>();

    public TreeNode reConstructBinaryTree(int[] pre, int[] in){
        for(int i = 0; i < in.length; i++)
            indexForInOrders.put(in[i],i);
        return reConstructBinaryTree(pre,0,pre.length - 1, 0);
    }

    private TreeNode reConstructBinaryTree(int[] pre, int preL,int preR, int inL){
        if(preL > preR)
            return null;
        TreeNode root = new TreeNode(pre[preL]);
        int inIndex = indexForInOrders.get(root.val);
        int leftTreeSize = inIndex - inL;
        root.left = reConstructBinaryTree(pre,preL + 1,preL + leftTreeSize,inL);
        root.right = reConstructBinaryTree(pre, preL + leftTreeSize + 1, preR, inL + leftTreeSize + 1);
        return root;
    }
}

代码二

public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        TreeNode root = reConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
        return root;
    }

    //前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
    private TreeNode reConstructBinaryTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {
        if (startPre > endPre || startIn > endIn) {
            return null;
        }
        TreeNode root = new TreeNode(pre[startPre]);

        for (int i = startIn; i <= endIn; i++) {
            if (in[i] == pre[startPre]){
                root.left = reConstructBinaryTree(pre,startPre + 1,startPre + i - startIn,in,startIn,i-1);
                root.right = reConstructBinaryTree(pre,i-startIn + startPre + 1,endPre,in,i+1,endIn);
                break;
            }
        }
        return root;
    }
本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 剑指Offer:重建二叉树

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多