LeetCode_Stack_331. Verify Preorder Serialization of a Binary Tree 驗證二叉樹的前序序列化（Java）【棧，字元串處理】

目錄

​​一，題目描述​​

​​英文描述​​

​​中文描述​​

​​示例與說明​​

​​二，解題思路​​

​​1，棧合并節點​​

​​2，計算入度出度和​​

​​三，AC代碼​​

​​Java​​

​​棧​​

​​計算出入度​​

​​四，解題過程​​

​​第一博​​

​​第二搏​​

一，題目描述

英文描述

One way to serialize a binary tree is to use preorder traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as '#'.

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where '#' represents a null node.

Given a string of comma-separated values preorder, return true if it is a correct preorder traversal serialization of a binary tree.

It is guaranteed that each comma-separated value in the string must be either an integer or a character '#' representing null pointer.

You may assume that the input format is always valid.

For example, it could never contain two consecutive commas, such as "1,,3".

Note: You are not allowed to reconstruct the tree.

中文描述

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

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

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

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

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

示例與說明

來源：力扣（LeetCode）

連結：​​​https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree​​ 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。 

二，解題思路

1，棧合并節點

算法思路很簡單，直接上圖：

一個葉子節點+兩個空節點 轉化為一個空節點，自底向上 ，直到最終化簡為一個空節點。

2，計算入度出度和

參考​​@負雪明燭【 拍案叫絕的兩種解法：「棧」和「入度出度」】​​

三，AC代碼

Java

棧

class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] tree = preorder.split(",");
        Deque<String> record = new LinkedList<>();
        for (int i = 0; i < tree.length; i++) {
            if (!tree[i].equals("#")) record.push(tree[i]);
            else {
                if (!record.isEmpty() && record.peek().equals("#")) {
                    while (!record.isEmpty() && record.peek().equals("#")) {
                        if (record.size() < 2) return false;
                        record.pop();
                        record.pop();
                    }
                    record.push("#");
                } else record.push(tree[i]);
            }
            // System.out.println("----------------");
            // System.out.println(record.toString());
        }
        return record.size() == 1 && record.peek().equals("#");
    }
}

// 另一種更簡潔的實作方式
class Solution {
    public boolean isValidSerialization(String preorder) {
        LinkedList<String> stack = new LinkedList<>();
        for (String s : preorder.split(",")) {
            stack.push(s);
            while (stack.size() >= 3
                    && stack.get(0).equals("#")
                    && stack.get(1).equals("#")
                    && !stack.get(2).equals("#")) {
                stack.pop();
                stack.pop();
                stack.pop();
                stack.push("#");
            }
        }
        return stack.size() == 1 && stack.pop().equals("#");
    }
}      

計算出入度

// 錯誤的實作方法，比如測試用例為"#,7,6,9,#,#,#"
// class Solution {
//     public boolean isValidSerialization(String preorder) {
//         String[] tree = preorder.split(",");
//         int diff = 1;
//         for (int i = 0; i < tree.length; i++) {
//             if (tree[i].equals("#")) {
//                 diff -= 1;
//                 if (diff < 0) return false;
//             } else {
//                 diff += 1;
//             }
//             System.out.println(diff);
//         }
//         return diff == 0;
//     }
// }


class Solution {
    public boolean isValidSerialization(String preorder) {
        int diff = 1;
        for(String s : preorder.split(",")){
            diff--;// 這種直接先減一後面正常節點加2的方法 可以巧妙處理頭節點為空的用例
            if (diff < 0){
                return false;
            }
            if(!s.equals("#")){
                diff += 2;
            }
        }
        return diff == 0;
    }
}      

四，解題過程

第一博

老師上課講的使用棧的方法。細節部分調了很久

第二搏