手撸二叉树之从前序与中序遍历序列构造二叉树

HelloWorld杰少

关注

发布于: 2 小时前

Hello, 大家好，今天是我参加 9 月更文的第 12 天，今天给大家带来的关于二叉树相关的算法题是从前序与中序遍历构建二叉树，正文如下：

题目

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

解题思路

根据题意, 我们知道前序遍历的形式是先遍历根节点，然后是左子树，最后是右子树；中序遍历的形式是，先左子树，再根节点，最后是右节点；

只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。

这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。

在中序遍历中对根节点进行定位时，我们可以考虑使用哈希表来帮助我们快速地定位根节点。对于哈希映射中的每个键值对，键表示一个元素（节点的值），值表示其在中序遍历中的出现位置，代码实现如下：

代码实现

/** * 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();    int[] preOrder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {        for (int i = 0; i < inorder.length; i++) {            map.put(inorder[i], i);        }        this.preOrder = preorder;
        return helper(0, inorder.length - 1, 0, preOrder.length - 1);    }
    public TreeNode helper(int inStart, int inEnd, int preStart, int preEnd) {        if (inStart > inEnd || preStart > preEnd) return null;        int root = preOrder[preStart];         int pos = map.get(root);        TreeNode node = new TreeNode(root);        node.left = helper(inStart, pos - 1, preStart + 1, preStart + pos - inStart);        node.right = helper(pos + 1, inEnd, preStart + pos - inStart + 1, preEnd);        return node;    }}

复制代码

最后

复杂度分析：

时间复杂度：O(n)，其中 n 是树中的节点个数。
空间复杂度：O(n)，除去返回的答案需要的 O(n) 空间之外，我们还需要使用 O(n) 的空间存储哈希映射，以及 O(h)（其中 h 是树的高度）的空间表示递归时栈空间。这里 h < n，所以总空间复杂度为 O(n)。

发布于: 2 小时前阅读数: 2

原文链接:【http://xie.infoq.cn/article/9e2ebaecbf1abefea7c0d9e1f】。文章转载请联系作者。

HelloWorld杰少

关注

佛系编码 2019.05.13 加入

红鲤鱼与绿鲤鱼与驴。

发布

暂无评论

创作场景

手撸二叉树之从前序与中序遍历序列构造二叉树

题目

解题思路

代码实现

最后

HelloWorld杰少

评论