• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

剑指Offer:重建二叉树

极客题库 Geekerstar 8个月前 (08-28) 192次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

题目描述

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

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<Integer,Integer> 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;
    }

丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:剑指Offer:重建二叉树
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00