105. 从前序与中序遍历序列构造二叉树（高频题）

105. 从前序与中序遍历序列构造二叉树

• 解题思路
• 代码

解题思路

和剑指offer第七题一样

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    HashMap<Integer, Integer> map = new HashMap<>();//标记中序遍历
    int[] preorder;//保留的先序遍历

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            //将中序遍历的值及索引放在map中，方便递归时获取左子树与右子树的数量及其根的索引
            map.put(inorder[i], i);
        }
        /*三个索引分别为
        当前根的的索引
        递归树的左边界，即数组左边界
        递归树的右边界，即数组右边界*/
        return recursive(0, 0, inorder.length - 1);
    }

    TreeNode recursive(int pre_root, int in_left, int in_right) {
        if (in_left > in_right) {//越界了
            return null;
        }
        TreeNode root = new TreeNode(preorder[pre_root]);//获取root节点
        int idx = map.get(preorder[pre_root]);//获取在中序遍历中根节点所在索引，以方便获取左子树的数量

        //左子树的根的索引为先序中的根节点+1
        //递归左子树的左边界为原来的中序in_left
        //递归左子树的右边界为中序中的根节点索引-1
        root.left = recursive(pre_root + 1, in_left, idx - 1);
        //右子树的根的索引为先序中的 当前根位置 + 左子树的数量 + 1
        //递归右子树的左边界为中序中当前根节点+1
        //递归右子树的有边界为中序中原来右子树的边界
        root.right = recursive(pre_root + (idx - in_left) + 1, idx + 1, in_right);
        return root;

    }

    
}