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

难度: 🌕🌕

问题描述

---

解法 1 - 栈

class Solution {
    public boolean isValidSerialization(String preorder) {
        // 思路：
        // 借助 栈
        // 每次遇到 2 个连续的 # 说明该节点是叶子节点，弹出 # # cur
        // 弹出后，这边的子树就是空树了，可以用 # 代替
        // 如此循环，不断把叶子节点变为空节点，导致原有非叶子节点也渐渐变为空节点，直到为空树
        String[] arr = preorder.split(",");
        int len = arr.length;
        if(len == 1 && arr[0].equals("#")) {
            // 空树
            return true;
        }
        LinkedList<String> stack = new LinkedList<>();
        // 依次压栈
        for(int i = 0; i < len; i ++) {
            String cur = arr[i];
            while(!stack.isEmpty() && stack.peek().equals("#") && cur.equals("#")) {
                // 需要弹出该叶子节点，用空树代替
                stack.pop();
                // 弹出 2 个空节点后，需要保证当前节点为叶子节点，即有值，而非又是一个 #
                if(stack.isEmpty() || stack.peek().equals("#")) {
                    return false;
                }
                stack.pop(); // 弹出有效的叶子节点
            }
            stack.push(cur); // 压入当前字符串，不论是 值 还是 #
        }
        // 由于遍历到最后一个子串，无论如何都压入了最后一个元素，因此最终栈中只剩下最后的一个元素，而且必须是 #
        return stack.size() == 1 && stack.peek().equals("#");
    }
}

---

输出 1

---

解法 2 - 反序列化思路

class Solution {
    int index = 0;
    int len;
    public boolean isValidSerialization(String preorder) {
        // 思路：
        // 题意要求不重建树，但是我们按照建树的思路，看能否重建树，如果可以，说明满足条件
        String[] arr = preorder.split(",");
        len = arr.length;
        return mySol(arr) && index >= len; // 要保证遍历到最后一个元素
    }

    private boolean mySol(String[] arr) {
        // System.out.println(index);
        // 递归终止条件
        if(index >= len) {
            return false;
        }
        String cur = arr[index];
        if(cur.equals("#")) {
            // 说明是空节点，指针后移，该节点无需重建，更没有左右子树，直接返回
            index ++;
            return true;
        }
        // 到达这里，说明是一个有值的节点
        index ++;
        // 递归建立左右子树
        boolean left = mySol(arr);
        if(!left) {
            return false;
        }
        boolean right = mySol(arr);
        if(!right) {
            return false;
        }
        return true;
    }
}

---

输出