Question

331. Verify Preorder Serialization of a Binary Tree

中文文档

Description

One way to serialize a binary tree is to use preorder traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as '#'.

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where '#' represents a null node.

Given a string of comma-separated values preorder, return true if it is a correct preorder traversal serialization of a binary tree.

It is guaranteed that each comma-separated value in the string must be either an integer or a character '#' representing null pointer.

You may assume that the input format is always valid.

• For example, it could never contain two consecutive commas, such as "1,,3".

Note: You are not allowed to reconstruct the tree.

 

Example 1:

Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true

Example 2:

Input: preorder = "1,#"
Output: false

Example 3:

Input: preorder = "9,#,#,1"
Output: false

 

Constraints:

• 1 <= preorder.length <= 104
• preorder consist of integers in the range [0, 100] and '#' separated by commas ','.

Solutions

Solution 1

class Solution:
  def isValidSerialization(self, preorder: str) -> bool:
    stk = []
    for c in preorder.split(","):
      stk.append(c)
      while len(stk) > 2 and stk[-1] == stk[-2] == "#" and stk[-3] != "#":
        stk = stk[:-3]
        stk.append("#")
    return len(stk) == 1 and stk[0] == "#"

class Solution {
  public boolean isValidSerialization(String preorder) {
    String[] strs = preorder.split(",");
    int diff = 1;
    for (String s : strs) {
      if (--diff < 0) {
        return false;
      }
      if (!s.equals("#")) {
        diff += 2;
      }
    }
    return diff == 0;
  }
}

class Solution {
public:
  bool isValidSerialization(string preorder) {
    vector<string> stk;
    stringstream ss(preorder);
    string s;
    while (getline(ss, s, ',')) {
      stk.push_back(s);
      while (stk.size() >= 3 && stk[stk.size() - 1] == "#" && stk[stk.size() - 2] == "#" && stk[stk.size() - 3] != "#") {
        stk.pop_back();
        stk.pop_back();
        stk.pop_back();
        stk.push_back("#");
      }
    }
    return stk.size() == 1 && stk[0] == "#";
  }
};

func isValidSerialization(preorder string) bool {
  stk := []string{}
  for _, s := range strings.Split(preorder, ",") {
    stk = append(stk, s)
    for len(stk) >= 3 && stk[len(stk)-1] == "#" && stk[len(stk)-2] == "#" && stk[len(stk)-3] != "#" {
      stk = stk[:len(stk)-3]
      stk = append(stk, "#")
    }
  }
  return len(stk) == 1 && stk[0] == "#"
}

Solution 2

class Solution {
  public boolean isValidSerialization(String preorder) {
    List<String> stk = new ArrayList<>();
    for (String s : preorder.split(",")) {
      stk.add(s);
      while (stk.size() >= 3 && stk.get(stk.size() - 1).equals("#")
        && stk.get(stk.size() - 2).equals("#") && !stk.get(stk.size() - 3).equals("#")) {
        stk.remove(stk.size() - 1);
        stk.remove(stk.size() - 1);
        stk.remove(stk.size() - 1);
        stk.add("#");
      }
    }
    return stk.size() == 1 && stk.get(0).equals("#");
  }
}