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

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算法

Java

• 递归
  官方题解：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9/

1、前序遍历数组的第一个节点是跟节点，根据跟节点的值确定其在中序遍历数组的索引
2、中序遍历数组中，根节点左侧的所有元素为根节点的左子树，根节点右侧的所有元素为根节点的右子树
3、根据中序遍历数组的根节点索引，将中序遍历数组切割为左子树数组，右子树数组
4、根据中序遍历数组的左右子树的数组，确定前序遍历数组中左右子树的数组
5、确定了根节点的左右子树的前序遍历数组和中序遍历数组，递归 1- 4步骤

class Solution {
    // 中序数组的哈希表，key：值；value：索引
    Map<Integer, Integer> map;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        // 遍历中序数组，缓存哈希表
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return buildTreHelper(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    private TreeNode buildTreHelper(int[] preorder, int p_start, int p_end, int[] inorder, int i_start, int i_end) {
        // 递归终结条件
        if (p_start == p_end || i_start == i_end) {
            return null;
        }
        // 确定root节点
        TreeNode root = new TreeNode(preorder[p_start]);
        // 根节点在中序数组的索引
        int rootIndex = map.get(root.val);
        // 左子树节点个数
        int leftCount = rootIndex - i_start;
        // 左子树
        root.left = buildTreHelper(preorder, p_start+1, p_start+1+leftCount, inorder, i_start, rootIndex);
        // 右子树
        root.right = buildTreHelper(preorder, p_start+leftCount+1, p_end, inorder, rootIndex+1, i_end);
        return root;
    }
}

GitHub：https://github.com/huxq-coder/LeetCode
欢迎star