C# O(n) time, O(n) stack space


  • 0
    C

    C# implementation based on similar idea I saw from postorder and inorder construction question

        public TreeNode BuildTree(int[] preorder, int[] inorder)
        {
            int pInorder = 0;
            int pPreorder = 0;
    
            return BuildTree(preorder, inorder, null, ref pPreorder, ref pInorder);
        }
    
        private TreeNode BuildTree(int[] preorder, int[] inorder, TreeNode end, ref int pPreorder, ref int pInorder)
        {
            if (pPreorder >= preorder.Length)
            {
                return null;
            }
    
            TreeNode n = new TreeNode(preorder[pPreorder++]);
    
            // left subtree exists
            if (inorder[pInorder] != n.val)
            {
                n.left = BuildTree(preorder, inorder, n, ref pPreorder, ref pInorder);
            }
    
            pInorder++;
    
            // right subtree exists
            if ((end == null) || (pInorder < inorder.Length && inorder[pInorder] != end.val))
            {
                n.right = BuildTree(preorder, inorder, end, ref pPreorder, ref pInorder);
            }
    
            return n;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.