331. 验证二叉树的前序序列化

[dutLyuyu]

331. 验证二叉树的前序序列化

思路

如输入： "9,3,4,#,#,1,#,#,2,#,6,#,#" ，当遇到 x,#,# 的时候，就把它变为 #。

模拟一遍过程：

[9,3,4,#,#] => [9,3,#]，继续
[9,3,#,1,#,#] => [9,3,#,#] => [9,#] ，继续
[9,#2,#,6,#,#] => [9,#,2,#,#] => [9,#,#] => [#]，结束

作者：fuxuemingzhu
链接：https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree/solution/pai-an-jiao-jue-de-liang-chong-jie-fa-zh-66nt/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码

/**
 * @param {string} preorder
 * @return {boolean}
 */
var isValidSerialization = function(preorder) {
    const order = preorder.split(','); 
    const stack = [];
    for (let i = 0; i < order.length; i++ ) {
        stack.push(order[i]);
        while(stack.length >= 3 && stack[stack.length - 1] === '#' && stack[stack.length - 2] === '#' && stack[stack.length - 3] !== '#') {
            stack[stack.length - 3] = '#';
            stack.pop();
            stack.pop();
        }
        
    }
    return stack.length === 1 && stack[0] === '#';
};