# ac solution code

• ``````    /*
Solution1. time = lgn(Division) * lgn(Search in in-order array) = O(n); space = O(1)
Same as pre-order, just take the root from the end of post-order array.

post-order array A: left right root
in-order  array  B: left root right

1) Find `root`: Take the last one of post-order as root
2) Search `root` in in-order array at i:
Divide A into left and right parts: "0..i-1, i+1..n-1"
Divide B into left and right parts: "0..i-1, i+1..n-1"
3) Keep the recursion with the above steps.
*/
func buildTree(_ inorder: [Int], _ postorder: [Int]) -> TreeNode? {
return buildTree(postorder, 0, postorder.count - 1, inorder, 0, inorder.count - 1)
}

func buildTree(_ postorder: [Int], _ postStart: Int, _ postEnd: Int, _ inorder: [Int], _ inStart: Int, _ inEnd: Int) -> TreeNode? {
guard inStart <= inEnd else {return nil} //<--
let root = TreeNode(postorder[postEnd]) // Take postorder.last as  root
let pos = findPos(postorder[postEnd], inorder, inStart, inEnd) // Find root index in inorder array

if pos != -1 {
if pos - 1 >= 0 {// build left branch <--postStart+pos-inStart-1
root.left = buildTree(postorder, postStart, postStart + pos - inStart - 1, inorder, inStart, pos - 1)
}
if pos + 1 <= inEnd {// build right branch <--
root.right = buildTree(postorder, postStart + pos - inStart, postEnd - 1, inorder, pos + 1, inEnd)
}
}
return root
}

/// Find position of key in inorder array with start/end bounds
func findPos(_ key: Int, _ inorder: [Int], _ inStart: Int, _ inEnd: Int) -> Int {
for i in inStart...inEnd where inorder[i] == key {
return i
}
return -1
}
``````

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