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

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

啊，好久都没有更新算法题目了。曾今是C++，如今是Java，感慨啊。

像树这样的算法题，基本都逃不开递归。递归的思想是：将大任务拆分为小任务。我们不妨构建一个函数，取名func1()，它实现的功能是:在指定区间内, 找到并构建root节点并返回。

如果我们想要构建一棵树，只需要调用func1()，就能够得到树的根节点，那么树的构建过程就可以简化为如下形式:

TreeNode root = new TreeNode();
root.value = value;
root.left = func1(...);
root.right = func1(...)'
1
2
3
4

通过func1，我们即可计算得到左右节点，具体的逻辑都一样

现在，让我们将视角聚焦于如何构建func1()。函数内容的核心是：构建root节点。构建分为三步: 1.得到root.val，构建root.left，构建root.right。为了解决这个内容，我们先将 前序遍历，中序遍历写为以下形式

前序 ： 【root，（左子树），（右子树）】
中序 ： 【（左子树），root，（右子树）】

如果我们想要确定root节点，我们只需要在前序数组中，获取第一个元素即可。如果我们想要确定左子树长度，右子树长度，我们只需要知道中序中，root节点的index即可

我们假设前序数组的区间范围是：$[l1,r1]$，中序是：$[l2,r2]$。root节点在中序的下标是$rootIdxIn$，那么左子树长度$lefLen=rootIndIn-l2$，右子树长度$rigLen=r2-rootIndIn$

rootValue很好获取，前序[l1]。
root.left的获取，我们可以交给递归函数完成。因为root.left，其本质是左子树的root节点，规定func1的计算范围是root节点的左子树范围即可完成计算；
root.right同理。

tip : 笔者习惯将递归函数命名为dfs，但这不是真正的dfs

/**
 * 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 {
    public HashMap<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 通过map映射 值-index的方式, 加速root节点在中序数组下标的定位速度
        for (int i = 0; i < inorder.length; ++i) {
            map.put(inorder[i], i);
        }
        return dfs(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    public TreeNode dfs(int[] preorder, int[] inorder, int l1, int r1, int l2, int r2) {
        // 递归终止条件, 如果l1 > r1, 表明当区间不存在, 节点值应该赋为null
        if (l1 > r1 || l2 > r2) return null;

        // debug
        System.out.println("l1 = " + l1 + " r1 = " + r1 + " l2 = " + l2 + " r2 = " + r2);

        // 确定根节点
        int rootVal = preorder[l1];
        // 根节点再inorder中的index
        int rootIdxIn = map.get(rootVal);

        System.out.println("rootIdxIn = " + rootIdxIn);

        // 左区间长度
        int lefLen = rootIdxIn - l2;
        // 右区间长度
        int rigLen = r2 - rootIdxIn;

        TreeNode root = new TreeNode();
        root.val = rootVal;
        root.left = dfs(preorder, inorder, l1 + 1, l1 + lefLen, l2, rootIdxIn - 1);
        root.right = dfs(preorder, inorder, l1 + lefLen + 1, r1, rootIdxIn + 1, r2);
        return root;
    }
}
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53