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

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

思路一：模拟 回想了一下学校老师上课讲的如何根据两个遍历序列还原出二叉树的：

1. 根据前序序列的第一个字符确定树的根，示例中的3。
2. 知道了3这个根，根据中序序列确定左右子树[9]是左子树、[15,20,7]是右子树。
3. 根据左子树前序序列第一个字符确定树的根：9。9的左右子树为null，左子树完毕。
4. 根据右子树前序序列第一个字符确定树的根：20。
5. 知道了20这个根，根据中序序列确定左右子树[15]是左子树、[7]是右子树。
6. 根据左子树前序序列第一个字符确定树的根：15。15的左右子树为null，左子树完毕。
7. 根据右子树前序序列第一个字符确定树的根：7。7的左右子树为null，左子树完毕。

这个过程就是在利用：前序序列[根左右]根在开头确定根、中序遍历[左根右]确定根的左右子树。

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

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

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder == null || preorder.length == 0
        || inorder == null || inorder.length == 0
        || preorder.length != inorder.length) return null;
    return build(preorder, 0, preorder.length - 1,
                 inorder, 0, inorder.length - 1);
}

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

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

---

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

更多题解和源码:github