leetcode-javascript/solutions/0536-construct-binary-tree-from-string.js at development · Anuj9826/leetcode-javascript · GitHub

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * Construct Binary Tree From String
 * Time Complexity: O(N)
 * Space Complexity: O(H)
 */
var str2tree = function (s) {
  if (!s) {
    return null;
  }

  let currentPointerIndex = 0;

  const parseValue = () => {
    let isNegativeValue = false;
    if (s[currentPointerIndex] === "-") {
      isNegativeValue = true;
      currentPointerIndex++;
    }

    let extractedNumber = 0;
    while (
      currentPointerIndex < s.length &&
      s[currentPointerIndex] >= "0" &&
      s[currentPointerIndex] <= "9"
    ) {
      extractedNumber = extractedNumber * 10 + parseInt(s[currentPointerIndex]);
      currentPointerIndex++;
    }

    return isNegativeValue ? -extractedNumber : extractedNumber;
  };

  const buildNode = () => {
    if (currentPointerIndex >= s.length) {
      return null;
    }

    const nodeValue = parseValue();
    const currentNode = new TreeNode(nodeValue);

    if (currentPointerIndex < s.length && s[currentPointerIndex] === "(") {
      currentPointerIndex++;
      currentNode.left = buildNode();
      currentPointerIndex++;
    }

    if (currentPointerIndex < s.length && s[currentPointerIndex] === "(") {
      currentPointerIndex++;
      currentNode.right = buildNode();
      currentPointerIndex++;
    }

    return currentNode;
  };

  return buildNode();
};