題目

https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/

題解

看了答案，參考：拍案叫絕的兩種解法：「棧」和「入度出度」

使用了一種重磅級(jí)的技巧：不斷地把有效的葉子節(jié)點(diǎn)使用 “#” 代替。 比如把 4## 替換成 # 。此時(shí)，葉子節(jié)點(diǎn)會(huì)變成空節(jié)點(diǎn)！

評(píng)論區(qū)有人把這個(gè)過(guò)程調(diào)侃為“合成大西瓜”，很形象。

class Solution {public boolean isValidSerialization(String preorder) {String[] tree = preorder.split(",");// 二叉樹(shù)的正確性與節(jié)點(diǎn)上的具體數(shù)字無(wú)關(guān)，故用bool區(qū)分是否為空節(jié)點(diǎn)即可LinkedList<Boolean> stack = new LinkedList<>();for (String c : tree) {if (c.equals("#")) stack.push(false);else stack.push(true);// "合成大西瓜"while (stack.size() > 2 && !stack.get(0) && !stack.get(1) && stack.get(2)) { stack.pop();stack.pop();stack.pop();stack.push(false);}}return stack.size() == 1 && !stack.pop();} }

總結(jié)

以上是生活随笔為你收集整理的leetcode 331. Verify Preorder Serialization of a Binary Tree | 331. 验证二叉树的前序序列化（栈解法）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。