331. Verify Preorder Serialization of a Binary Tree 发表于 2021-12-04 Stack1234567891011121314151617181920212223242526class Solution { public boolean isValidSerialization(String preorder) { String[] array = preorder.split(","); Deque<String> stack = new ArrayDeque<>(); for (String str : array) { stack.push(str); while (stack.size() >= 3) { String top1 = stack.pop(); String top2 = stack.pop(); String top3 = stack.pop(); if (top1.equals("#") && top2.equals("#") && !top3.equals("#")) { stack.push("#"); } else { stack.push(top3); stack.push(top2); stack.push(top1); break; // 注意需要 break 出 while 循环 } } } return stack.size() == 1 && stack.peek().equals("#"); }} Degree12345678910111213141516171819class Solution { public boolean isValidSerialization(String preorder) { // 所有节点的入度和与出度和应该相等 String[] array = preorder.split(","); int degreeDiff = 1; // 给 root 预留的入度 for (String s : array) { degreeDiff--; // 减去一个入度 if (degreeDiff < 0) { // 在遍历节点过程中,出度减入度应该大于等于 0 return false; } if (!s.equals("#")) { degreeDiff += 2; // 非空节点具有两个出度 } } return degreeDiff == 0; }} Reference331. Verify Preorder Serialization of a Binary Tree