樹的建構

LC 105 / 106   root = the next element of the pre/post-order array, split by its index in inorder
LC 654         root = the MAXIMUM of the range
LC 108         root = the MIDDLE of the range (sorted input -> balanced BST)
LC 536         root = the value before the first '(' — parentheses delimit the child ranges
LC 1597        root = the LAST lowest-precedence operator outside any parenthesis

// java
// LC 654 - Maximum Binary Tree
// IDEA: root of range [lo, hi] = the MAX element; recurse on the two sub-ranges
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        // time = O(N^2) worst case (already-sorted input), O(N log N) average
        // space = O(N) for the recursion stack in the worst case
        return build(nums, 0, nums.length - 1);
    }

    private TreeNode build(int[] nums, int lo, int hi) {
        if (lo > hi) return null;             // NOTE: empty range -> null child

        int idx = lo;                          // find index of max in [lo, hi]
        for (int i = lo + 1; i <= hi; i++) {
            if (nums[i] > nums[idx]) idx = i;
        }

        TreeNode root = new TreeNode(nums[idx]);
        root.left  = build(nums, lo, idx - 1);   // everything LEFT of the max
        root.right = build(nums, idx + 1, hi);   // everything RIGHT of the max
        return root;
    }
}

# python
# LC 654 - Maximum Binary Tree
# IDEA: pick max index as root of the range, recurse on left / right sub-ranges
class Solution:
    def constructMaximumBinaryTree(self, nums):
        # time = O(N^2) worst case, space = O(N)
        def build(lo, hi):
            if lo > hi:
                return None
            idx = lo
            for i in range(lo + 1, hi + 1):
                if nums[i] > nums[idx]:
                    idx = i
            root = TreeNode(nums[idx])
            root.left = build(lo, idx - 1)
            root.right = build(idx + 1, hi)
            return root

        return build(0, len(nums) - 1)

# python
# LC 108 - Convert Sorted Array to Binary Search Tree
# IDEA: same "build by index range" skeleton as LC 654, root = MIDDLE element
class Solution:
    def sortedArrayToBST(self, nums):
        # time = O(N), space = O(log N)
        def build(lo, hi):
            if lo > hi:
                return None
            mid = (lo + hi) // 2          # middle -> balanced tree
            root = TreeNode(nums[mid])
            root.left = build(lo, mid - 1)
            root.right = build(mid + 1, hi)
            return root

        return build(0, len(nums) - 1)

#  Construct Binary Tree from Preorder and Inorder Traversal
# V0
# IDEA: the pre-order head is the root; its position in in-order splits the
#       remaining elements into the two subtrees. LC 105 builds a GENERAL binary
#       tree -- no BST ordering is assumed or required.
# time = O(N^2), space = O(N^2)
#   -> `inorder.index` rescans the range on every call and each recursion copies
#      four slices. Readable, but NOT the O(N) the table above quotes -- that is
#      the Java form below, which passes index bounds and a value -> index map.
class Solution(object):
    def buildTree(self, preorder, inorder):
        if len(preorder) == 0:
            return None
        if len(preorder) == 1:
            return TreeNode(preorder[0])
        ### NOTE : init root like below (via TreeNode and root value (preorder[0]))
        root = TreeNode(preorder[0])
        # get the index of root.val in order to SPLIT TREE
        index = inorder.index(root.val)  # the index of root at inorder, and we can also get the length of left-sub-tree, right-sub-tree ( preorder[1:index+1]) for following using
        # recursion for root.left
        #### NOTE : preorder[1 : index + 1] (for left sub tree)
        root.left = self.buildTree(preorder[1 : index + 1], inorder[ : index]) ### the two traversals cover the SAME elements, so the left subtree has the same length in both -- that is what lets one index split both arrays
        # recursion for root.right 
        root.right = self.buildTree(preorder[index + 1 : ], inorder[index + 1 :]) ### same on the right: everything after `index` in in-order is the right subtree
        return root

// Java - Build Tree from Preorder and Inorder
private int preIndex = 0;
private Map<Integer, Integer> inorderMap = new HashMap<>();

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

private TreeNode build(int[] preorder, int left, int right) {
    if (left > right) return null;

    int rootVal = preorder[preIndex++];
    TreeNode root = new TreeNode(rootVal);

    int index = inorderMap.get(rootVal);

    root.left = build(preorder, left, index - 1);
    root.right = build(preorder, index + 1, right);

    return root;
}

def build_tree_post(inorder, postorder):
    if not inorder or not postorder:
        return None

    # Last element in postorder is root
    root_val = postorder[-1]
    root = TreeNode(root_val)

    root_index = inorder.index(root_val)

    root.left = build_tree_post(inorder[:root_index], postorder[:root_index])
    root.right = build_tree_post(inorder[root_index+1:], postorder[root_index:-1])

    return root

tree   := number ( '(' tree ')' )? ( '(' tree ')' )?
number := '-'? digit+

        0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
   s =  4 ( 2 ( 3 ) ( 1 ) )  (  6  (  5  )  )

parse(i=0)  num "4"        -> i=1
  s[1]=='(' -> i=2, recurse LEFT
  parse(i=2)  num "2"      -> i=3
    s[3]=='(' -> i=4, recurse LEFT
    parse(i=4)  num "3"    -> i=5   s[5]==')' -> no children, return (3, 5)
    i=5 -> skip ')' -> i=6
    s[6]=='(' -> i=7, recurse RIGHT
    parse(i=7)  num "1"    -> i=8   s[8]==')' -> return (1, 8)
    i=8 -> skip ')' -> i=9
  return (2, 9)
  i=9 -> skip ')' -> i=10
  s[10]=='(' -> i=11, recurse RIGHT
  parse(i=11) num "6"      -> i=12
    s[12]=='(' -> i=13, recurse LEFT
    parse(i=13) num "5"    -> i=14  return (5, 14)
    i=14 -> skip ')' -> i=15
  return (6, 15)
  i=15 -> skip ')' -> i=16 == len -> done

parse(i):
    consume the ATOM at i            # number, letter, literal
    while next char opens a group:   # '(' , '[' , '{'
        i += 1                       # eat the opener
        child, i = parse(i)          # recurse
        i += 1                       # eat the closer
    return built_node, i

# LC 1597 Build Binary Expression Tree From Infix Expression
# V0
# IDEA : LC 224 Basic Calculator
class Solution(object):

    def help(self, numSt, opSt):
        right = numSt.pop()
        left = numSt.pop()
        # Node(val=op, left=lhs, right=rhs)
        return Node(opSt.pop(), left, right)

    def expTree(self, s):
        # hashmap for operator ordering
        pr = {'*': 1, '/': 1, '+': 2, '-': 2, ')': 3, '(': 4}
        numSt = []
        opSt = []
        i = 0
        while i < len(s):
            c = s[i]
            i += 1
            # check if int(c) if string
            if c.isnumeric():
                numSt.append(Node(c))
            else:                
                if c == '(':
                    opSt.append('(')
                else:
                    while(len(opSt) > 0 and pr[c] >= pr[opSt[-1]]):
                        numSt.append(self.help(numSt, opSt))
                    if c == ')':
                        opSt.pop() # Now what remains is the closing bracket ')'
                    else:
                        opSt.append(c)
        while len(opSt) > 0:
            numSt.append(self.help(numSt, opSt))
        print (">>> numSt = {}, opSt = {}".format(str(numSt), opSt))
        return numSt.pop()

# V0'
# IDEA : RECURSIVE
class Solution:
    def expTree(self, s):
        n = len(s)
        if n == 1:
            return Node(s)

        fstOpIdx = None
        kets = 0
        for i in range(n-1, 0, -1):
            if s[i] == ")":
                kets += 1
            elif s[i] == "(":
                kets -= 1
            elif kets == 0:
                if s[i] in "+-":
                    fstOpIdx = i
                    break
                elif s[i] in "*/" and fstOpIdx is None:
                    fstOpIdx = i
        if fstOpIdx is None:
            return self.expTree(s[1:-1])
        rtNd = Node(s[fstOpIdx])
        rtNd.left = self.expTree(s[:fstOpIdx])
        rtNd.right = self.expTree(s[fstOpIdx+1:])
        return rtNd