Skip to content

Instantly share code, notes, and snippets.

@wovalle

wovalle/CH4113N93-1337.js

Last active May 24, 2020 20:10
Show Gist options
  • Save wovalle/a86a76bc20d8c886342040f54875f291 to your computer and use it in GitHub Desktop.
Save wovalle/a86a76bc20d8c886342040f54875f291 to your computer and use it in GitHub Desktop.
Download ZIP
LeetCode May 2020
Raw
CH4113N93-1337.js
// LeetCode May 2020
@wovalle
Copy link
Author

wovalle commented May 24, 2020 

// 24.js
const getLast = (arr, level = 1) => (arr.length ? arr[arr.length - level] : null);
const bstFromPreorder = function (preorder) {
  if (!preorder.length) {
    return null;
  }

  const leaves = [[new TreeNode(preorder.shift()), -Infinity, Infinity]];

  while (preorder.length) {
    const currentVal = preorder.shift();

    while (currentVal > getLast(leaves)[2] || currentVal < getLast(leaves)[1]) {
      leaves.pop();
    }

    const [leave, min, max] = getLast(leaves);

    if (currentVal > leave.val) {
      leave.right = new TreeNode(currentVal);
      leaves.push([leave.right, leave.val, max]);
    } else if (currentVal < leave.val) {
      leave.left = new TreeNode(currentVal);
      leaves.push([leave.left, min, leave.val]);
    }
  }

  return leaves[0][0];
};

// Time: O(n)
// Space: O(n)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment