验证二叉树的前序序列化

2021-03-31

题目描述：

序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

例如，上面的二叉树可以被序列化为字符串 “9,3,4,#,#,1,#,#,2,#,6,#,#”，其中 # 代表一个空节点。
给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 ‘#’ 。
你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 “1,,3” 。

示例
示例 1:
输入: “9,3,4,#,#,1,#,#,2,#,6,#,#”
输出: true
示例 2：
输入: “1,#”
输出: false

解法思路：

我们可以利用栈的特性来完成这件事，前序遍历的顺序是中前后。我们可以在栈中记录一个数字，
代表当前节点可能有几个节点。首先我们存入一个1代表根节点。然后我们开始遍历字符串，如果我们遇到”#”就代表这个节点是空节点，我们就需要将栈顶的元素进行减一，代表我们已经找到了一个子节点。如果我们遇到的是数字，就代表当前节点不为空，我们就需要将栈顶的数字进行减一，代表我们已经找到了一个子节点，并且一个不为空的节点可能有两个子节点，所以我们要在栈中再压入一个2.我们需要判断每次遍历栈顶元素是否为0，如果为0代表这个中间节点的两个子节点都找到了，当前节点的遍历完成。要进行出栈操作。到最后我们就判断栈中是否还有元素即可，如果还有说明序列错误。

const isValidSerialization = function (preorder) {
    //1、创建栈,并初始化它，1代表根节点(不管根节点是否为空)
    let stack = [1];
    let n = preorder.length;
    let i = 0;
    //2、遍历字符串
    while (i < n) {
        //判空:如果字符串还没遍历完栈就为空，则代表这个序列是错误的(出现1, #, #, #, #情况)
        if (!stack.length) return false;
        //如果当前字符串为“,”的话，则跳过它，不做任何操作
        if (preorder[i] === ',') {
            i++;
        } else if (preorder[i] === '#') {
            //如果是“#”号的话，就说明改井号是当前栈首元素的子节点，则把当前栈首的值-1
            stack[stack.length - 1] -= 1;
            //-1后还需要判断是否为0了，为0代表当前栈首位置的子节点都已经遍历过了
            if (stack[stack.length - 1] === 0) {
                //为0，出栈
                stack.pop();
            }
            i++;
        } else {
            //当遇到数字的时候，我们已经知道要把当前的栈首值减一，且入栈一个2,那么当前i需要移动到后面去
            while (i < n && preorder[i] !== ',') {
                i++;
            }
            //否则就为数字
            //数字代表的是一个非空节点，那么它可能还有两个子节点，所以需要把当前栈首的值-1后，再入栈一个2
            stack[stack.length - 1] -= 1;
            if (stack[stack.length - 1] === 0) {
                stack.pop();
            }
            stack.push(2);
        }
    }
    //遍历完成后，栈应该为空才是，如果不为空说明序列错误
    return !stack.length;
}

另外解题思路：每次拆掉⼀个“数字、#、#”的节点（即叶⼦结点），最后树上的全部节点都会被拆光（即只剩⼀个“#”），能拆光的序列就是合法序列。