Golang (3 ms) solution. Easy to understand.

  • 0

    The basic idea is to construct the tree from the preorderNull string using a stack.

      Scan "backward" from the end
          if '#'
              Push null node to the stack.
              Pop two nodes from the stack as the children of this non-null node.
              (If the stack underflows here, return false right away.)
              Push the non-null node back to the stack.
      Once the input is completely consumed, the stack shuold only contain the root node.

    However, we don't really need to construct the tree, but to monitor the depth of stack.

    func isValidSerialization(preorder string) bool {
        p := strings.Split(preorder, ",")
        var depth int
        for i := len(p) - 1; i >= 0; i-- {
            if p[i] == "#" {
                depth++ // Push to the stack.
            } else if depth < 2 {
                return false // Stack underflow.
            } else {
                // Pop two nodes, and push a new node back to the Stack.
                depth = depth - 2 + 1
        return depth == 1 // Valid if only one node (root) left in the stack.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.