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

祝你万事顺利

发布于 2019-06-13 20:50:22

4030

发布于 2019-06-13 20:50:22

文章被收录于专栏：Unity游戏开发

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

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

例如，给出

前序遍历 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);
        }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019.06.12 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法