# Question

Formatted question description: https://leetcode.ca/all/105.html

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]


Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]


Constraints:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder and inorder consist of unique values.
• Each value of inorder also appears in preorder.
• preorder is guaranteed to be the preorder traversal of the tree.
• inorder is guaranteed to be the inorder traversal of the tree.

# Algorithm

Since the first in the order of preorder must be the root, the root node of the original binary tree can be known. A very critical condition is given in the title that there are no identical elements in the tree.

With this condition, it can be traversed in the middle order. Locate the position of the root node, and split the in-order traversal into the left and right parts according to the position of the root node, and call the original function on it recursively.

### Note

The pitfall is that I traverse the inorder and find the position of root

• But pre.length/2 is wrong, the midpoint is not necessarily directly divided by 2, because the binary tree may not be left-right balanced
• So find root from preorder, and then find root in inorder. In inorder, the ones before root are all children on the left

# Code

• import java.util.Arrays;

public class Construct_Binary_Tree_from_Preorder_and_Inorder_Traversal {

/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {

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

TreeNode buildTree(int[] preorder, int pLeft, int pRight, int[] inorder, int iLeft, int iRight) {
if (pLeft > pRight || iLeft > iRight) return null;

int i = 0;
for (i = iLeft; i <= iRight; ++i) {
if (preorder[pLeft] == inorder[i]) break;
}

TreeNode cur = new TreeNode(preorder[pLeft]);

cur.left = buildTree(preorder, pLeft + 1, pLeft + (i - iLeft), inorder, iLeft, i - 1);
cur.right = buildTree(preorder, pLeft + (i - iLeft) + 1, pRight, inorder, i + 1, iRight);
return cur;
}
}
}

############

/**
* Definition for a binary tree node.
* public 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;
*     }
* }
*/
class Solution {
private Map<Integer, Integer> indexes = new HashMap<>();

public TreeNode buildTree(int[] preorder, int[] inorder) {
for (int i = 0; i < inorder.length; ++i) {
indexes.put(inorder[i], i);
}
return dfs(preorder, inorder, 0, 0, preorder.length);
}

private TreeNode dfs(int[] preorder, int[] inorder, int i, int j, int n) {
if (n <= 0) {
return null;
}
int v = preorder[i];
int k = indexes.get(v);
TreeNode root = new TreeNode(v);
root.left = dfs(preorder, inorder, i + 1, j, k - j);
root.right = dfs(preorder, inorder, i + 1 + k - j, k + 1, n - k + j - 1);
return root;
}
}

• # 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

# best
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder: # or, not inorder
return None
v = preorder[0]
i = inorder.index(v)
root = TreeNode(v)
root.left = self.buildTree(preorder[1: i+1], inorder[:i])
root.right = self.buildTree(preorder[i+1:], inorder[i+1:])
return root

# inorder.index(preorder_val)
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
def dfs(pleft, pright, ileft, iright):
if pleft > pright or ileft > iright:
return None
k = inorder.index(preorder[pleft])
root = TreeNode(preorder[pleft])
root.left = dfs(pleft + 1, pleft + (k - ileft), ileft, k - 1)
root.right = dfs(pleft + 1 + (k - ileft), pright, k + 1, iright)
return root

n = len(preorder)
return dfs(0, n - 1, 0, n - 1)

# build dict for val => index
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
def dfs(pleft, pright, ileft, iright):
if pleft > pright or ileft > iright:
return None
v = preorder[pleft]
k = d[v]
root = TreeNode(v)
root.left = dfs(pleft + 1, pleft + (k - ileft), ileft, k - 1)
root.right = dfs(pleft + 1 + (k - ileft), pright, k + 1, iright)
return root

d = {v: i for i, v in enumerate(inorder)}
n = len(preorder)
return dfs(0, n - 1, 0, n - 1)

############

'''
search for index, also use .index(val)
>>> a = [1,2,3,4,5]
>>> a.index(3)
2
'''
class Solution(object):
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""

self.preindex = 0
ind = {v: i for i, v in enumerate(inorder)}
head = self.dc(0, len(preorder) - 1, preorder, inorder, ind)

def dc(self, start, end, preorder, inorder, ind):
if start <= end:
mid = ind[preorder[self.preindex]]
self.preindex += 1
root = TreeNode(inorder[mid])
root.left = self.dc(start, mid - 1, preorder, inorder, ind)
root.right = self.dc(mid + 1, end, preorder, inorder, ind)
return root


• /**
* 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) {}
* };
*/
class Solution {
public:
unordered_map<int, int> indexes;

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for (int i = 0; i < inorder.size(); ++i) indexes[inorder[i]] = i;
return dfs(preorder, inorder, 0, 0, inorder.size());
}

TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int i, int j, int n) {
if (n <= 0) return nullptr;
int v = preorder[i];
int k = indexes[v];
TreeNode* root = new TreeNode(v);
root->left = dfs(preorder, inorder, i + 1, j, k - j);
root->right = dfs(preorder, inorder, i + 1 + k - j, k + 1, n - k + j - 1);
return root;
}
};

• /**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func buildTree(preorder []int, inorder []int) *TreeNode {
indexes := make(map[int]int)
for i, v := range inorder {
indexes[v] = i
}
var dfs func(i, j, n int) *TreeNode
dfs = func(i, j, n int) *TreeNode {
if n <= 0 {
return nil
}
v := preorder[i]
k := indexes[v]
root := &TreeNode{Val: v}
root.Left = dfs(i+1, j, k-j)
root.Right = dfs(i+1+k-j, k+1, n-k+j-1)
return root
}
return dfs(0, 0, len(inorder))
}

• /**
* Definition for a binary tree node.
* class TreeNode {
*     val: number
*     left: TreeNode | null
*     right: TreeNode | null
*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
*         this.val = (val===undefined ? 0 : val)
*         this.left = (left===undefined ? null : left)
*         this.right = (right===undefined ? null : right)
*     }
* }
*/

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
const n = preorder.length;
if (n === 0) {
return null;
}
const val = preorder[0];
const index = inorder.indexOf(val);
return new TreeNode(
val,
buildTree(preorder.slice(1, index + 1), inorder.slice(0, index)),
buildTree(preorder.slice(index + 1), inorder.slice(index + 1)),
);
}


• /**
* 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)
* }
*/
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
var buildTree = function (preorder, inorder) {
function dfs(i, j, n) {
if (n <= 0) {
return null;
}
const v = preorder[i];
const k = d[v];
const root = new TreeNode(v);
root.left = dfs(i + 1, j, k - j);
root.right = dfs(i + 1 + k - j, k + 1, n - k + j - 1);
return root;
}
const d = new Map();
for (const [i, v] of inorder.entries()) {
d[v] = i;
}
return dfs(0, 0, inorder.length);
};


• // 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
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
fn to_tree(preorder: &[i32], inorder: &[i32]) -> Option<Rc<RefCell<TreeNode>>> {
if preorder.is_empty() {
return None;
}
let val = preorder[0];
let index = inorder.iter().position(|&v| v == val).unwrap();
Some(Rc::new(RefCell::new(TreeNode {
val,
left: Self::to_tree(&preorder[1..index + 1], &inorder[..index]),
right: Self::to_tree(&preorder[index + 1..], &inorder[index + 1..]),
})))
}

pub fn build_tree(preorder: Vec<i32>, inorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
Self::to_tree(&preorder[..], &inorder[..])
}
}