长大后想做什么？做回小孩！

0%

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

发表于 分类于 Valine：
本文字数： 235

NO.106 从中序与后序遍历序列构造二叉树 中等

J91a38.png

思路一：模拟 和NO.105采用相同的思路。

利用：后序序列[左右根]根在结尾确定根、中序遍历[左根右]确定根的左右子树。

实现的过程其实就是：先根据后序序列确定根，再根据中序序列确定根的左子树or右子树，再将左子树or右子树对应的后序序列区间和中序序列区间重复前两步。。。。

明显是个递归结构，递归出口是：后序或中序序列的区间为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public TreeNode buildTree(int[] inorder, int[] postorder) {
    if (inorder == null || inorder.length == 0
        || postorder == null || postorder.length == 0
        || inorder.length != postorder.length) return null;
    return build(inorder, 0, inorder.length - 1,
                 postorder, 0, postorder.length - 1);
}

private TreeNode build(int[] inorder, int iStart, int iEnd, int[] postorder, int pStart, int pEnd) {
    //递归出口
    if (iEnd < iStart || pEnd < pStart) return null;
    //根据后序序列确定根
    TreeNode root = new TreeNode(postorder[pEnd]);
    //找到中序序列中根的位置
    int idx = 0;
    while (inorder[iStart + idx] != postorder[pEnd]) idx++;
    //生成根的左右子树
    root.left = build(inorder, iStart, iStart + idx - 1,
                      postorder, pStart, pStart + idx - 1);
    root.right = build(inorder, iStart + idx + 1, iEnd,
                       postorder, pStart + idx, pEnd - 1);
    return root;
}

时间复杂度：O(n) 两个序列遍历一次

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github