331. 驗證二叉樹的前序序列化

序列化二叉樹的一種方法是使用前序周遊。當我們遇到一個非空節點時，我們可以記錄下這個節點的值。如果它是一個空節點，我們可以使用一個标記值記錄，例如 #。

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

例如，上面的二叉樹可以被序列化為字元串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一個空節點。

給定一串以逗号分隔的序列，驗證它是否是正确的二叉樹的前序序列化。編寫一個在不重構樹的條件下的可行算法。

每個以逗号分隔的字元或為一個整數或為一個表示 null 指針的 '#' 。

你可以認為輸入格式總是有效的，例如它永遠不會包含兩個連續的逗号，比如 "1,,3" 。

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

棧

import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public boolean isValidSerialization(String preorder) {
        int n = preorder.length();
        int i = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(1);
        while (i < n) {
            if (stack.isEmpty()) {
                return false;
            }
            if (preorder.charAt(i) == ',') {
                i++;
            } else if (preorder.charAt(i) == '#') {
                int top = stack.pop() - 1;
                if (top > 0) {
                    stack.push(top);
                }
                i++;
            } else {
                // 讀一個數字
                while (i < n && preorder.charAt(i) != ',') {
                    i++;
                }
                int top = stack.pop() - 1;
                if (top > 0) {
                    stack.push(top);
                }
                stack.push(2);
            }
        }
        return stack.isEmpty();
    }
}
           

計數

class Solution {
    public boolean isValidSerialization(String preorder) {
        int n = preorder.length();
        int i = 0;
        int slots = 1;
        while (i < n) {
            if (slots == 0) {
                return false;
            }
            if (preorder.charAt(i) == ',') {
                i++;
            } else if (preorder.charAt(i) == '#') {
                slots--;
                i++;
            } else {
                // 讀一個數字
                while (i < n && preorder.charAt(i) != ',') {
                    i++;
                }
                slots++; // slots = slots - 1 + 2
            }
        }
        return slots == 0;
    }
}
           

心之所向，素履以往 生如逆旅，一葦以航