剑指offer07.重建二叉树

一 思路

看到二叉树首先想到遍历操作 BFS DFS;由前序和中序重建二叉树，首先想到的是 root根节点，前序第一个便是root根节点，根据root找到 中序位置，能够得到左右子树，可以根据左右子树依次进行遍历。

二 难点

怎么选择重建二叉树操作？ 左右子树节点位置的考虑分析

三 结果

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private Map<Integer, Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //二叉树长度
        int n = preorder.length;
        map = new HashMap<Integer, Integer>();
        //
        for (int i = 0; i < n; i++) {
            //快速定位到对应的根节点
            map.put(inorder[i], i);
        }

        return myBuildTree(preorder,inorder,0,n-1,0,n-1);
    }

    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        //已遍历至根节点完毕
        if (preorder_left > preorder_right) {
            return null;
        }
        int pre_root = preorder_left;
        //根据前序的root节点 求出中序的root节点位置
        int inorder_root = map.get(preorder[pre_root]);

        //建立root节点关联
        TreeNode root = new TreeNode(preorder[pre_root]);

        //计算左右子树的节点位置
        int size_left_subtree = inorder_root - inorder_left;

        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);

        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_root);
        return root;
    }
}

加油，坚持 一步一步来