专栏首页Unity游戏开发105. 从前序与中序遍历序列构造二叉树

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

根据一棵树的前序遍历与中序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如,给出

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树:

2Tree.PNG

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode BuildTree(int[] preorder, int[] inorder) {
        
    }
}
public class Solution {
        int index = 0;
        List<int> mPre = new List<int>();
        List<int> mIn = new List<int>();
        Dictionary<int, int> dic = new Dictionary<int, int>();
        private TreeNode BuildNode(int left, int right)
        {
            if (left == right)
            {
                return null;
            }
            TreeNode treeNode = new TreeNode(mPre[index]);
            int temp = dic[mPre[index]];
            index++;
            treeNode.left = BuildNode(left, temp);
            treeNode.right = BuildNode(temp + 1, right);
            return treeNode;
        }
        public TreeNode BuildTree(int[] preorder, int[] inorder)
        {
            for (int i = 0; i < preorder.Length; i++)
            {
                mPre.Add(preorder[i]);
                mIn.Add(inorder[i]);

                dic.Add(inorder[i], i);
            }
            return BuildNode(0, preorder.Length);
        }
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C#-面向对象编程、接口、泛型

    1 开闭原则:对扩展开放,对修改(old Code)关闭 2 类的单一职责:每个类有且只有一个改变它的原因 3 优先使用组合而非继承: 避免耦合度过高 4...

    祝你万事顺利
  • C#-委托与事件

    委托:是一个类、是一种数据类型 定义语法: 访问修饰符 关键字(delegate) 返回值 标识符(参数列表) 委托的绑定:和委托的返回值一样,参数一样的方...

    祝你万事顺利
  • 771. Jewels and Stones

    You're given strings J representing the types of stones that are jewels, and S r...

    祝你万事顺利
  • 1062. 昂贵的聘礼

    思路: 实际上是一个图模型,采用递归,物品之间的交换有一条关系边,比如国王需要物品2,那么可以用8000来交换,此时子问题就变成了从物品2出发,所需要的最少...

    用户1147447
  • 贪心算法总结贪心算法基本思路算法实现实例分析参考

    贪心算法 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。...

    致Great
  • 挑战程序竞赛系列(59):4.6树上的分治法(2)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • POJ 刷题系列:1789. Truck History

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • POJ 刷题系列:2002. Squares

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 4.7后缀数组

    第一次接触后缀数组,采用《挑战》P378的后缀算法,时间复杂度为O(nlog2n)O(n\log^2n),基本思想如下:

    用户1147447
  • 【2020HBU天梯赛训练】7-50 部落

    在一个社区里,每个人都有自己的小圈子,还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里,于是要请你统计一下,在一个给定社区中,到底有多少个互不...

    韩旭051

扫码关注云+社区

领取腾讯云代金券