二刷

2種做法，indegree outdegree是一種。

public class Solution {public boolean isValidSerialization(String preorder) {if(preorder.length() == 0) return true;String[] noodArray = preorder.split(",");int indegree = 0;int outdegree = 1;for(int i = 0; i < noodArray.length;i++){if(outdegree - indegree < 1) return false;char tempChar = noodArray[i].charAt(0);if(tempChar == '#') indegree++;else{outdegree+=2;indegree++;}}if(indegree == outdegree) return true;else return false;} }

具體是判斷能不能再添加了。
標準是outdegree - indegree > 0

OUT算是可用的，IN是用掉的，只要還有可用的，就可以繼續添加。

然后最后out == in才行。

初始自動給個out =1 in = 0，給的那個1是為了添加ROOT的。

另一個方法是Stack。

因為是preOrder，所以push到stack過程中，如果數量多余3個，就有潛在的可以剪枝的機會，剪枝機會的表現是：
stack頂端的3個是

數字
。

說明這個子樹是符合規定的，那么把這個子樹直接變成1個#，然后push回去。

只在多余3的情況考慮。

最終STACK里剩下1個#就說明符合了。很新穎的思路,具體實現方法，一刷里有。

---

---

三刷。

記憶力不行，這個題記得是in/out degree來做的，這么做也確實方便。

沒添加一個NODE會增加1個in-Degree，如果添加的不是null會增加2個out-Degree.

out-Degree > in-Degree說明有多余的out-Degree等待添加Node，所以可以繼續添加。

注意初始是outDegree - inDgree = 1. 相當于初始給個支來添加Root..

然后添加的時候要先判斷，再添加。。最后in-Degree == out-Degree才行。

public class Solution {public boolean isValidSerialization(String preorder) {if (preorder.length() == 0) return true;int inDegree = 0;int outDegree = 1;for (String s : preorder.split(",")) {inDegree ++;if (outDegree - inDegree < 0) return false;if (!s.equals("#")) outDegree += 2;}return inDegree == outDegree;} }

看二刷說第二個做法是preOrder，這樣當棧頂是2個# #的時候，說明可以剪掉這個分支，這里的剪掉不是backtrack，是cut，cut your balls的cut。

挖槽，做了好久，里面的邏輯有點混亂。。

public class Solution {public boolean isValidSerialization(String preorder) {if (preorder.length() == 0) return true;Stack<String> stk = new Stack<>();String[] str = preorder.split(",");for (int i = 0; i < str.length; i++) {String s = str[i];stk.push(s);while (stk.size() >= 3 && s.equals("#")) {String s1 = stk.pop();String s2 = stk.pop();String s3 = stk.pop();if (s2.equals("#") && !s3.equals("#")) {stk.push("#");} else if (s2.equals("#") && s3.equals("#")) {return false;} else {stk.push(s3);stk.push(s2);stk.push(s1);break;}}}return stk.size() == 1 && stk.peek().equals("#");} }

轉載于:https://www.cnblogs.com/reboot329/p/6112095.html

總結

以上是生活随笔為你收集整理的331. Verify Preorder Serialization of a Binary Tree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。