Massive Algorithms: Valid Preorder traversal serialized String

http://www.cnblogs.com/EdwardLiu/p/5138501.html

1 求问下各位大神，怎么判断一个按照Preorder traversal serialized的binary tree的序列是否正确呢？不能deserialize成树比如
2 A） 9 3 4 # # 1 # # 2 # 6 # #是对的，因为表示
3            9
4          /   \
5        3      2
6       /  \      \
7     4    1      6    
8 B ) 9 3 4 # # 1 # #就是错的，因为无法反构造回一棵树

我觉得可以在字符串里找"n##"这种结构（对应tree里两个children都是Null的叶节点），找到之后就把"n##"改写成"#"，也就是把找到的那个末端的子树想想成null，最后字符串变成"#"的就是valid，否则就invalid
比如 A) 9 3 "4 # #" "1 # #" 2 # "6 # #" ---> 9 3 # # 2 # # ---> 9 "3 # #" "2 # #" ---> 9 # # ---> "9 # #" ---> "#"
B) 9 3 "4 # #" "1 # #" ---> 9 3 # # ---> 9 "3 # #" ---> 9 # (没有"n##"结构了，return false)

也可用stack来这样做，当前如果是#,stack peek如果也是#且size>=2，就pop两次，且再check当前这个#

 5     public boolean check(String str) {
 6         String[] strs = str.split(" ");
 7         Stack<String> stack = new Stack<String>();
 8         for (int i=0; i<strs.length; i++) {
 9             if (stack.size()>=2 && strs[i].equals("#") && stack.peek().equals("#")) {
10                 stack.pop();
11                 stack.pop();
12                 i--;
13             }
14             else stack.push(strs[i]);
15         }
16         if (stack.size()==1 && stack.peek().equals("#")) return true;
17         else return false;
18     }

Valid Preorder traversal serialized String

Labels

Popular Posts