package fundamentals.tree.dfs.preorder.lc331_verifypreorderserializationofabinarytree;

import java.util.Stack;

/**
 * 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.
 */
public class Solution {

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

    // Neat and smart solution from dietpepsi!
    // Check if outdegree = indegree along the preorder path
    // which means every subtree must follow that rule
    public boolean isValidSerialization(String preorder) {
        int diff = 1;   // a "virtual" indegree for root
        for (String node : preorder.split(",")) {
            if (--diff < 0) {
                return false;
            }
            diff += "#".equals(node) ? 0 : 2;
        }
        return diff == 0;
    }

    // My 2AC: use a variable stack (or called depth)
    public boolean isValidSerialization2(String preorder) {
        String[] nodes = preorder.split(",");
        int stack = 0, i = 0;
        for (; i < nodes.length; i++) {
            if ("#".equals(nodes[i])) {
                if (stack == 0) {
                    break;
                }
                stack--;
            } else {
                stack++;
            }
        }
        return stack == 0 && i == nodes.length - 1 && "#".equals(nodes[i]);
    }

    // My 1AC: a real stack is overkill here.
    public boolean isValidSerialization1(String preorder) {
        Stack<String> stack = new Stack<>();
        String[] serial = preorder.split(",");

        int i = 0;
        while (i < serial.length && (!stack.isEmpty() || !serial[i].equals("#"))) {
            if (!serial[i].equals("#")) {
                stack.push(serial[i]);
                i++;
            } else { // stack must not be empty
                stack.pop();
                i++;
            }
        }
        // Stack is empty && i points to last && last is "#" => true!
        return (i == serial.length - 1);
    }

}

@@ -1294,24 +1294,1076 @@
 %22));%0A    %7D%0A%0A
+    // 1) non-null node contributes 2 outdegree and 1 indegree (2 children and 1 parent), except root%0A    // 2) all null node contributes 0 outdegree and 1 indegree (0 child and 1 parent).%0A    // If a serialization is correct, diff should never be negative and diff will be zero when finished%0A    public boolean isValidSerialization(String preorder) %7B%0A        int diff = 1; // a %22virtual%22 indegree for root%0A        for (String node : preorder.split(%22,%22)) %7B%0A            if (--diff %3C 0) return false;%0A            if (!%22#%22.equals(node)) diff += 2;%0A        %7D%0A        return diff == 0;%0A    %7D%0A%0A    // 3AC still use stack%0A    public boolean isValidSerialization_stack(String preorder) %7B%0A        String%5B%5D tree = preorder.split(%22,%22);%0A        int i = 0, stack = 0;%0A        for (; i %3C tree.length - 1; i++) %7B%0A            if (%22#%22.equals(tree%5Bi%5D)) %7B%0A                if (stack == 0) break;%0A                stack--;%0A            %7D else %7B%0A                stack++;%0A            %7D%0A        %7D%0A        return stack == 0 && i == tree.length - 1 && %22#%22.equals(tree%5Bi%5D);%0A    %7D%0A%0A
     // Neat 
@@ -2544,32 +2544,39 @@
 lidSerialization
+_degree
 (String preorder

verify preorder serialization of a binary tree