LeetCode: Construct Binary Tree from String

Posted on May 15, 2018July 26, 2020 by braindenny

Construct Binary Tree from String

Similar Problems:

You need to construct a binary tree from a string consisting of parenthesis and integers.

The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root’s value and a pair of parenthesis contains a child binary tree with the same structure.

You always start to construct the left child node of the parent first if it exists.

Example:

Input: "4(2(3)(1))(6(5))"
Output: return the tree root node representing the following tree:

       4
     /   \
    2     6
   / \   / 
  3   1 5

Note:

There will only be ‘(‘, ‘)’, ‘-‘ and ‘0’ ~ ‘9’ in the input string.
An empty tree is represented by “” instead of “()”.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

// https://code.dennyzhang.com/construct-binary-tree-from-string
// Basic Ideas: stack + post-order
//
//  L-R-M
//    (X X X)
//    (X X)
//    (X)
// When push back, it would be a TreeNode pointer
//
// Complexity: Time O(n), Space O(n)
//
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
import "strconv"
type MyNode struct {
    node *TreeNode
    isLeft bool
}

func str2tree(s string) *TreeNode {
    if len(s) == 0 {
        return nil
    }
    stack := []*MyNode{}
    for i:=0; i<len(s); i++ {
        ch := s[i]
        if ch != ')' {
            myNode := &MyNode{node:nil, isLeft:true}
            if ch != '(' {
                bytes := []byte{ch}
                for i+1<len(s) && s[i+1] != ')' && s[i+1] != '(' {
                    bytes = append(bytes, s[i+1])
                    i++
                }
                v, _ := strconv.Atoi(string(bytes))
                myNode = &MyNode{node:&TreeNode{Val:v}, isLeft:false}
            }
            stack = append(stack, myNode)
        } else {
            l := []*MyNode{}
            for ! stack[len(stack)-1].isLeft {
                l = append([]*MyNode{stack[len(stack)-1]}, l...)
                stack = stack[0:len(stack)-1]
            }
            // pop )
            stack = stack[0:len(stack)-1]
            if len(l) >= 2 {
                l[0].node.Left = l[1].node
            }
            if len(l) == 3 {
                l[0].node.Right = l[2].node
            }
            stack = append(stack, l[0])
        }
    }
    // get result
    l := stack
    if len(l) >= 2 {
        l[0].node.Left = l[1].node
    }
    if len(l) == 3 {
        l[0].node.Right = l[2].node
    }
    return l[0].node
}

Post Views: 6