leetCode-331:Verify Preorder Serialization of a Binary Tree

问题描述

给定一个字符串，字符串是用 , 分割的数字和 #，判断该字符串是否一个二叉树的前序遍历字符串（前序遍历过程中遇到空节点输出 #），要求在判断过程中不能将字符串转换为二叉树。题目链接：点我

样例输入输出

输入：preorder = “9,3,4,#,#,1,#,#,2,#,6,#,#”

输出：true

解释：该字符串代表的树形状如下

输入：preorder = “9,#,#,1”

输出：false

问题解法

用栈来模拟树的遍历过程，如果遇到 # ，则判断当前栈顶元素是否“暴露”了两次，如果是，说明当前节点的子节点已经遍历完成，将其出栈。最后判断栈中是否为空，如果为空，则说明是一个二叉树，否则不是。代码如下

class Solution {
    public boolean isValidSerialization(String preorder) {
        if (preorder.equals("#")) {
            return true;
        }

        String[] items = preorder.split(",");
        int[] counts = new int[101];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < items.length; i++) {
            String item = items[i];
            if (item.equals("#")) {
                if (stack.isEmpty()) {
                    return false;
                }
                counts[stack.peek()]++;
                
                // 可能存在重复的数字，所以用2的倍数来判断
                while (counts[stack.peek()] % 2 == 0) {
                    stack.pop();
                    
                    // 如果遍历过程中栈为空，还有剩余元素没入栈，说明这不是一棵二叉树
                    if (stack.isEmpty()) {
                        return i == items.length - 1;
                    }
                    counts[stack.peek()]++;
                }
            } else {
                stack.push(Integer.parseInt(item));
            }
        }

        return stack.isEmpty();
    }
}