从中序与后序遍历序列构造二叉树

发表于 更新于
本文字数： 3.7k 阅读时长 ≈ 3 分钟

LeetCode每日一题，106. Construct Binary Tree from Inorder and Postorder Treversal

先看题目描述

大意就是给定一棵二叉树的中序遍历序列和后序遍历序列，让我们将二叉树还原

算法和思路

我们得先了解中序遍历和后序遍历，中序遍历就是对一棵二叉树按左根右的顺序遍历，后序遍历就是对一棵二叉树按左右根的顺序进行遍历。由这个遍历顺序我们不难发现，一棵树的后序遍历序列中的最后一个节点就是根节点，而中序遍历序列中根节点会在中间部分，根节点的的左边部分是其左子树的所有节点，右边部分是其右子树的所有节点。那么我们就可以先根据后序遍历序列找出树的根节点，然后根据中序遍历序列将左子树和右子树的所有节点找出来，并可得到他们的中序遍历序列和后序遍历序列，然后再递归的构建左子树和右子树就可以

算法源码

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int len = postorder.length;
        if (len == 0) return null;
        int val = postorder[len - 1];
        TreeNode root = new TreeNode(val);
        if (len == 1) return root;
        int index = 0;
        for (int i = 0; i < len; i++) {
            if (inorder[i] == val) {
                index = i;
                break;
            }
        }
        int[] leftInorder = new int[index];
        int[] leftPostOrder = new int[index];
        int[] rightInorder = new int[len - index - 1];
        int[] rightPostOrder = new int[len - index - 1];
        for (int i = 0; i < len; i++) {
            if (i < index) {
                leftInorder[i] = inorder[i];
                leftPostOrder[i] = postorder[i];
            } else if (i == index) {
                if (len > index + 1) rightPostOrder[i - index] = postorder[i];
            } else if (i < len - 1) {
                rightPostOrder[i - index] = postorder[i];
                rightInorder[i- index - 1] = inorder[i];
            } else {
                rightInorder[len - index - 2] = inorder[i];
            }
        }
        root.left = buildTree(leftInorder, leftPostOrder);
        root.right = buildTree(rightInorder, rightPostOrder);
        return root;
    }
}

但这个的效率并不优秀，因为每次要重复的遍历中序遍历序列来寻找根节点下标

  • 定义一个变量 post_idx，初始化为 n - 1，表示后序遍历序列中当前根节点所在下标

  • 为了高效查找根节点元素在中序遍历数组中的下标，我们可以创建哈希表来存储中序序列

  • 定义递归函数 dfs(left, right) 表示当前递归到中序序列中当前子树的左右边界，递归入口为 dfs(0, n - 1) ：

    • 计算 [left, right] 区间的长度 len
    • 如果 len 与 0相等，直接返回空节点
    • 选择后序遍历中下标为 post_idx 的节点作为根节点
    • post_idx = post_idx - 1
    • 利用哈希表查找当前根节点在中序遍历序列中的下标 index，[0, index - 1] 为左子树部分，[index + 1, right] 为右子树部分
    • 根据后序遍历逻辑，递归创建右子树 dfs(index + 1, right) 和左子树 dfs(left, index - 1)。注意这里有需要先创建右子树，再创建左子树的依赖关系。可以理解为在后序遍历的数组中整个数组是先存储左子树的节点，再存储右子树的节点，最后存储根节点，如果按每次选择「后序遍历的最后一个节点」为根节点，则先被构造出来的应该为右子树
    • 返回 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
import java.util.*;

/**
 * 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> map = new HashMap<>();
    private int[] inorder;
    private int[] postorder;
    private int post_idx;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.inorder = inorder;
        this.postorder = postorder;
        int len = postorder.length;
        post_idx = postorder.length - 1;
        for (int i = 0; i < len; i++) {
            map.put(inorder[i], i);
        }
        return dfs(0, len - 1);
    }

    private TreeNode dfs(int left, int right) {
        int len = right - left + 1;
        if (len == 0) return null;
        int val = postorder[post_idx];
        post_idx--;
        TreeNode root = new TreeNode(val);
        if (len == 1) return root;
        int index = map.get(val);
        root.right = dfs(index + 1, right);
        root.left = dfs(left, index - 1);
        return root;
    }
}