[LeetCode] Construct Binary Tree from Inorder and Postorder Traversal

链接https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/ 难度:Medium 题目:106. Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

翻译:给定树的中序遍历和后序遍历,构造二叉树。 注意:树中不存在重复项。

思路:本题与105. Construct Binary Tree from Preorder and Inorder Traversal类似。你要先知道

中序遍历:左子树,根节点,右子树 后序遍历:左子树,右子树,根节点

以如下这棵树为例:

            1
    --------|-------
    2               3
----|----       ----|----
4       5       6       7

前序遍历 1245367 中序遍历 4251637 后续遍历 4526731

我们可以发现,对于后序遍历来说,最后一个元素一定是根节点,也就是1。然后我们在中序遍历的结果里面找到1所在的位置,那么它的左半部分就是其左子树,右半部分就是其右子树。 我们将中序遍历左半部分425取出,同时发现后序遍历的结果也在相应的位置上面,只是顺序稍微不一样,也就是452。我们可以发现,后序遍历中的2就是该子树的根节点。 上面说到了左子树,对于右子树,我们取出637,同时发现后序遍历中对应的数据偏移了一格,并且顺序也不一样,为673。而3就是这颗右子树的根节点。 重复上述过程,通过后续遍历找到根节点,然后在中序遍历数据中根据根节点拆分成两个部分,同时将对应的后序遍历的数据也拆分成两个部分,重复递归,就可以得到整个二叉树了。

参考代码: Java

/**
 * 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) {
        Map<Integer, Integer> inorderMap = new HashMap<Integer, Integer>();
        for(int i=0; i<inorder.length; i++)
            inorderMap.put(inorder[i],i);
        return buildTree(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1, inorderMap);

    }

    public TreeNode buildTree(int[] inorder, int iLeft, int iRight, int[] postorder, int pLeft, int pRight, Map<Integer, Integer> inorderMap){
        if(iLeft>iRight || pLeft>pRight)
            return null;
        TreeNode cur = new TreeNode(postorder[pRight]);
        //int i = 0;
        //for(i=iLeft; i<=iRight; i++)
        //   if(postorder[pRight]==inorder[i])
        //        break;
        int i = inorderMap.get(postorder[pRight]);
        cur.left = buildTree(inorder, iLeft, i-1, postorder, pLeft, pLeft+i-iLeft-1, inorderMap);
        cur.right = buildTree(inorder, i+1, iRight, postorder, pLeft+i-iLeft, pRight-1, inorderMap);
        return cur;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏尾尾部落

[剑指offer] 二叉树中和为某一值的路径

输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

9010
来自专栏gaoqin31

二叉查找树

高:ni的高是从ni到一片树叶的最长路径的长,因此,所有叶子的高为0,一颗树的高等于它的根的高

9220
来自专栏一英里广度一英寸深度的学习

二叉树添加删除节点Python

采用递归调用实现二叉树添加、删除节点。文章采用Python对象引用方式实现指针结构的创建。

59520
来自专栏分布式系统进阶

Librdkafka的基础数据结构 1 --- 队列

两个元素: tqh_first: 指向队列的第一个成员; tqh_last: 存的是队列里的最后一个元素的 next指针的变量地址, 这个二级指针太有用了,...

12620
来自专栏个人分享

二叉树的深度

输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

10920
来自专栏尾尾部落

[剑指offer] 二叉搜索树的后序遍历序列

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

23920
来自专栏WD学习记录

牛客网 二叉树的深度

输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

9510
来自专栏一英里广度一英寸深度的学习

二叉树的深度优先遍历与广度优先遍历

先遍历子节点,再遍历兄弟节点。 从根节点开始递归,如果存在子节点,继续遍历子节点。

97130
来自专栏AI星球

如何实现大数据集查询?Bloom Filter或许是你想要的

虽然上面描述的这几种数据结构配合常见的排序、二分搜索可以快速高效的处理绝大部分判断元素是否存在集合中的需求。但是当集合里面的元素数量足够大,如果有500万条记录...

23550
来自专栏haifeiWu与他朋友们的专栏

《剑指Offer》50道算法面试题

《剑指Offer》50道算法面试题 - C++版,本来一开始想用Java来写,不过看看了,JDK里封装了很多算法,用Java写就没意思了,于是用选择了C++,顺...

1.9K20

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励