此篇博客主要记录剑指offer中遇到的不会的题。

 

一、重建二叉树（剑指offer 07）

medium  2021-06-22

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

　　解题思路：前序遍历的特点，根节点在第一位； 中序遍历的特点，根节点在中间，左右子树分别在两侧。

　　　　可以先利用前序遍历找出根节点，然后递归寻找左右子树的根节点。

　　　　这个题我断断续续写了两三天都没写出来，放弃了

　　

class Solution {
    private Map<Integer, Integer> indexMap;
    public TreeNode myBuildTree(int[] preorder, int[] inorder, int pre_left, int pre_right, int in_left,
                               int in_right){
        if(pre_left > pre_right){
            return null;
        }
        int pre_root = pre_left; //最左边的序号就是这个子树的根节点的序号
        int in_root = indexMap.get(preorder[pre_root]);//找到中序遍历的根节点
        int left_tree_length = in_root - in_left; //左子树的长度
        TreeNode root = new TreeNode(preorder[pre_root]);
        root.left = myBuildTree(preorder, inorder, pre_left + 1, pre_left + left_tree_length,
                               in_left, in_root - 1);
        root.right = myBuildTree(preorder, inorder,pre_left + left_tree_length + 1, pre_right, 
                                in_root + 1, in_right);
        return root;   
    }   
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        indexMap = new HashMap<>();
        for(int i = 0; i < n; i++){
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
}