leetcode VerifyPreorderSerializationofaBinaryTree
z
 2019-04-09 10:36:27   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import java.util.Stack;

public class VerifyPreorderSerializationofaBinaryTree {
  /**
   * 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:
   *
   * Input: "9,3,4,#,#,1,#,#,2,#,6,#,#"
   * Output: true
   * Example 2:
   *
   * Input: "1,#"
   * Output: false
   * Example 3:
   *
   * Input: "9,#,#,1"
   * Output: false
   */
  public static boolean isValidSerialization(String preorder) {
    Stack<String> stack = new Stack<String>();
    String[] sc = preorder.split(",");
    if (sc.length < 3) return false;
    for (String c: sc){
      if ("#".equals(c)){

        if (stack.size() == 0) return false;
        if (!"#".equals(stack.peek())){
          stack.push(c);
        }
        else{
          if (stack.size() < 2) return false;
          String a = stack.pop();
          String b = stack.pop();
          while ("#".equals(a) && !"#".equals(b) && stack.size()>=2){
            a = stack.pop();
            b = stack.pop();
          }
          if (! ("#".equals(a)&&!"#".equals(b))){
            stack.push(b);
            stack.push(a);
            stack.push(c);
          }
          else{
            stack.push(c);
          }

        }
      }
      else{
        stack.push(c);
      }
      for (String i: stack){
        System.out.print("stack: " + i + " ");
      }
      System.out.println();
    }
    if (stack.size() == 1 && "#".equals(stack.pop())){
      return true;
    }
    return false;

  }
  public static void main(String[] args){
    String[] test = new String[]{"9,3,4,#,#,1,#,#,2,#,6,#,#","1,#","9,#,#,1"};
    for (String s : test){
      System.out.println(isValidSerialization(s));
    }
  }
}