题解 | #重建二叉树 (Java 递归)#

重建二叉树

http://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6

import java.util.*;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {

    private Map<Integer, Integer> indexMap; // 使用map加快查找速度

    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {

        int n = in.length;
        indexMap = new HashMap<>();

        for (int i = 0; i < n; i++) {
            indexMap.put(in[i], i);
        }

        return rebuildTree (pre, in, 0, n - 1, 0, n - 1);
    }

    private TreeNode rebuildTree (int [] pre,int [] in, int pl, int pr, int il, int ir) {

        if (pl > pr) {
            return null;
        }

        TreeNode root = new TreeNode(pre[pl]); // 先序数组的第一元素就是根节点root

        int inRootIndex = indexMap.get(pre[pl]); // 根节点在中序数组中的下标

        int leftTreeSize = inRootIndex - il; // 以这次的root为根节点的左子树的大小

        root.left = rebuildTree(pre, in, pl + 1, pl + leftTreeSize, il, inRootIndex - 1); // 递归重建左子树
        root.right = rebuildTree(pre, in, pl + leftTreeSize + 1, pr, inRootIndex + 1, ir); // 递归重建右子树

        return root;
    }
}
全部评论

相关推荐

06-12 16:23
已编辑
小米_软件开发(准入职员工)
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务