Leetcode 106 - Construct binary tree from inorder and postorder traversal

Note

  • The last element of postorder is the current root.
  • Steps
    • Get the root
    • Split inorder array based on its value, then we have leftSubtreeInorder and rightSubtreeInorder.
    • Based on the length of them, we can get leftSubtreePostorder and rightSubtreePostorder.

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

Example

img

1
2
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* 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[]} inorder
* @param {number[]} postorder
* @return {TreeNode}
*/
var buildTree = function(inorder, postorder) {
return traverse(inorder, postorder);

function traverse(inorderArr, postorderArr) {
/* Base situation1: When both arrays are empty */
if (inorderArr.length === 0 && postorderArr.length === 0) return null;

const rootVal = postorderArr.pop();
let root = new TreeNode(rootVal);
/* Base situation2: When only one node left */
if (postorderArr.length === 0) {
return root;
}

const rootIndex = inorderArr.indexOf(rootVal);

let leftInorder = inorderArr.slice(0, rootIndex);
let rightInorder = inorderArr.slice(rootIndex + 1);
let leftPostOrder = postorderArr.slice(0, leftInorder.length);
let rightPostOrder = postorderArr.slice(leftInorder.length);
root.left = traverse(leftInorder, leftPostOrder);
root.right = traverse(rightInorder, rightPostOrder);

return root;
}
};