剑指offer 面试题7 重建二叉树

剑指offer60天计划

Posted by liuwenzi on July 23, 2020
阅读数:

重建二叉树

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

例如,给出

1
2
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

题解

  • 递归

    • 前序遍历的第一个节点就是根节点,在中序遍历中根节点的位置的左边就是二叉树的左子树
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        private HashMap<Integer,Integer> hashMap = new HashMap();
        private int[] preorder_copy;
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            preorder_copy = preorder;
            for(int i = 0; i < preorder.length ; i++){
                hashMap.put(inorder[i],i);
            }
            return buildSubtree(0,0,inorder.length-1);
        }
        TreeNode buildSubtree(int pre_root,int in_left,int in_right){
            if(in_left > in_right){
                return null;
            }
            TreeNode root = new TreeNode(preorder_copy[pre_root]);
            int in_root = hashMap.get(preorder_copy[pre_root]);
            root.left = buildSubtree(pre_root + 1,in_left,in_root-1);
          	//pre_root + in_root - in_left + 1 代表右子树的根节点在前序遍历序列中的位置
            root.right = buildSubtree(pre_root + in_root - in_left + 1,in_root+1,in_right );
            return root;   
        }
      
    }
    

    zoB34g

模板

总结

这题之前做过,重新回来做一遍,发现自己思路很清晰,但是具体的写法忘了,花了好多的时间,最后看了别人的做法才做出来。看来还是要总结写题模板。