105. Inorder preorder build

105_solution1.c

#include "tree_node.h"
#include <stdlib.h>

#define OFFSET 3000 // constraint: -3000 <= node values <= 3000

static struct TreeNode *build(int *preorder, int *preIdx, int inLo, int inHi,
                              int *inIndex) {
  if (inLo > inHi)
    return NULL;

  int rootVal = preorder[(*preIdx)++];
  int mid = inIndex[rootVal + OFFSET];

  struct TreeNode *cur = malloc(sizeof(struct TreeNode));
  cur->val = rootVal;
  cur->left = build(preorder, preIdx, inLo, mid - 1, inIndex);
  cur->right = build(preorder, preIdx, mid + 1, inHi, inIndex);
  return cur;
}

struct TreeNode *buildTree(int *preorder, int preorderSize, int *inorder,
                           int inorderSize) {
  static int inIndex[2 * OFFSET + 1];
  for (int i = 0; i < inorderSize; i++)
    inIndex[inorder[i] + OFFSET] = i;

  int preIdx = 0;
  return build(preorder, &preIdx, 0, inorderSize - 1, inIndex);
}

tree_node.h

#pragma once

#include <stddef.h>

// Definition for a binary tree node.
struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
};

105_solution1.cpp

#include "tree_node.h"
#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
  TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
    unordered_map<int, int> idxs;

    for (int i = 0; i < inorder.size(); i++)
      idxs[inorder[i]] = i;

    int preIdx = 0;
    return build(preorder, preIdx, 0, (int)inorder.size() - 1, idxs);
  }

  TreeNode *build(vector<int> &preorder, int &preIdx, int inLo, int inHi,
                  unordered_map<int, int> &inIndex) {
    if (inLo > inHi)
      return nullptr;

    int rootVal = preorder[preIdx++];
    int mid = inIndex[rootVal];

    TreeNode *cur = new TreeNode(rootVal);
    cur->left = build(preorder, preIdx, inLo, mid - 1, inIndex);
    cur->right = build(preorder, preIdx, mid + 1, inHi, inIndex);
    return cur;
  }
};

tree_node.h

#pragma once

// Definition for a binary tree node.
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};

105_solution1.go

package trees

func buildTree(preorder []int, inorder []int) *TreeNode {
    inIndex := make(map[int]int, len(inorder))
    for i, v := range inorder {
        inIndex[v] = i
    }

    preIdx := 0
    var build func(inLo, inHi int) *TreeNode
    build = func(inLo, inHi int) *TreeNode {
        if inLo > inHi {
            return nil
        }

        rootVal := preorder[preIdx]
        preIdx++
        mid := inIndex[rootVal]

        cur := &TreeNode{Val: rootVal}
        cur.Left = build(inLo, mid-1)
        cur.Right = build(mid+1, inHi)
        return cur
    }

    return build(0, len(inorder)-1)
}

tree_node.go

package trees

// Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

105_solution1.java

import java.util.HashMap;
import java.util.Map;

class Solution {
    private Map<Integer, Integer> inIndex;
    private int preIdx;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        inIndex = new HashMap<>();
        for (int i = 0; i < inorder.length; i++)
            inIndex.put(inorder[i], i);

        preIdx = 0;
        return build(preorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int inLo, int inHi) {
        if (inLo > inHi)
            return null;

        int rootVal = preorder[preIdx++];
        int mid = inIndex.get(rootVal);

        TreeNode cur = new TreeNode(rootVal);
        cur.left = build(preorder, inLo, mid - 1);
        cur.right = build(preorder, mid + 1, inHi);
        return cur;
    }
}

TreeNode.java

// Definition for a binary tree node.
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;
    }
}

105_solution1.js

const TreeNode = require("./tree_node");

var buildTree = function (preorder, inorder) {
  const inIndex = new Map();
  inorder.forEach((v, i) => inIndex.set(v, i));

  let preIdx = 0;
  const build = (inLo, inHi) => {
    if (inLo > inHi) return null;

    const rootVal = preorder[preIdx++];
    const mid = inIndex.get(rootVal);

    const cur = new TreeNode(rootVal);
    cur.left = build(inLo, mid - 1);
    cur.right = build(mid + 1, inHi);
    return cur;
  };

  return build(0, inorder.length - 1);
};

tree_node.js

// Definition for a binary tree node.
function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val;
  this.left = left === undefined ? null : left;
  this.right = right === undefined ? null : right;
}

module.exports = TreeNode;

105_solution1.py

from typing import List, Optional

from tree_node import TreeNode


class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        in_index = {v: i for i, v in enumerate(inorder)}
        pre_idx = 0

        def build(in_lo: int, in_hi: int) -> Optional[TreeNode]:
            nonlocal pre_idx
            if in_lo > in_hi:
                return None

            root_val = preorder[pre_idx]
            pre_idx += 1
            mid = in_index[root_val]

            cur = TreeNode(root_val)
            cur.left = build(in_lo, mid - 1)
            cur.right = build(mid + 1, in_hi)
            return cur

        return build(0, len(inorder) - 1)

tree_node.py

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

105_solution1.rs

use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;

use crate::tree_node::TreeNode;

type Link = Option<Rc<RefCell<TreeNode>>>;

impl Solution {
    pub fn build_tree(preorder: Vec<i32>, inorder: Vec<i32>) -> Link {
        let in_index: HashMap<i32, i32> = inorder
            .iter()
            .enumerate()
            .map(|(i, &v)| (v, i as i32))
            .collect();

        let mut pre_idx = 0;
        Self::build(&preorder, &mut pre_idx, 0, inorder.len() as i32 - 1, &in_index)
    }

    fn build(
        preorder: &[i32],
        pre_idx: &mut usize,
        in_lo: i32,
        in_hi: i32,
        in_index: &HashMap<i32, i32>,
    ) -> Link {
        if in_lo > in_hi {
            return None;
        }

        let root_val = preorder[*pre_idx];
        *pre_idx += 1;
        let mid = in_index[&root_val];

        let mut cur = TreeNode::new(root_val);
        cur.left = Self::build(preorder, pre_idx, in_lo, mid - 1, in_index);
        cur.right = Self::build(preorder, pre_idx, mid + 1, in_hi, in_index);
        Some(Rc::new(RefCell::new(cur)))
    }
}

tree_node.rs

use std::cell::RefCell;
use std::rc::Rc;

// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}