One way to serialize a binary tree is to use pre-order 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 #
.
_9_
/ \
3 2
/ \ / \
4 1 # 6
/ \ / \ / \
# # # # # #
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, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.
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"
.
Example 1:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true
Example 2:
"1,#"
Return false
Example 3:
"9,#,#,1"
Return false
class Node{
String val;
boolean left;
public Node(String s){
left = false;
val = s;
}
}
public boolean isValidSerialization(String preorder) {
//use stack to store parent when we hit '#', '#' we pop parent
//when we hit '#', we know parent has gone through one part, if we went left before we pop
if(preorder.equals("#")) return true;
Stack<Node> stack = new Stack<>();
String s = "";
for(int i = 0 ; i < preorder.length(); i++){
char c = preorder.charAt(i);
if(c == ','){
stack.push(new Node(s));
s="";
}else if(c == '#'){
i++;
if(stack.empty()) return false;
while(!stack.empty() && stack.peek().left){
stack.pop();
}
if(!stack.empty())
stack.peek().left = true;
if(stack.empty() && i < preorder.length()-1)
return false;
}else{
s += c;
}
}
return stack.empty()&&s.equals("");
}
存‘#’当作flag表示左边已经走完
public class Solution {
public boolean isValidSerialization(String preorder) {
if (preorder == null) {
return false;
}
Stack<String> st = new Stack<>();
String[] strs = preorder.split(",");
for (int pos = 0; pos < strs.length; pos++) {
String curr = strs[pos];
while (curr.equals("#") && !st.isEmpty() && st.peek().equals(curr)) {
st.pop();
if (st.isEmpty()) {
return false;
}
st.pop();
}
st.push(curr);
}
return st.size() == 1 && st.peek().equals("#");
}
}
NO Stack
https://discuss.leetcode.com/topic/35976/7-lines-easy-java-solution/2
Some used stack. Some used the depth of a stack. Here I use a different perspective. In a binary tree, if we consider null as leaves, then
- all non-null node provides 2 outdegree and 1 indegree (2 children and 1 parent), except root
- all null node provides 0 outdegree and 1 indegree (0 child and 1 parent).
Suppose we try to build this tree. During building, we record the difference between out degree and in degree diff
= outdegree - indegree
. When the next node comes, we then decrease diff
by 1, because the node provides an in degree. If the node is notnull
, we increase diff by 2
, because it provides two out degrees. If a serialization is correct, diff should never be negative and diff will be zero when finished.
public boolean isValidSerialization(String preorder) {
String[] nodes = preorder.split(",");
int diff = 1;
for (String node: nodes) {
if (--diff < 0) return false;
if (!node.equals("#")) diff += 2;
}
return diff == 0;
}