資訊專欄INFORMATION COLUMN
摘要：令，那么從累加會(huì)一直保持正，最后為。從左往右比較好理解，因?yàn)榭偸强偟阶笤俚接遥目偸堑?，所以一定是保持。注意從開(kāi)始，因?yàn)闆](méi)有。
Verify Preorder Serialization of a Binary Tree
題目鏈接：https://leetcode.com/problems...
recursion，用個(gè)全局的index：
public class Solution {
public boolean isValidSerialization(String preorder) {
if(preorder == null || preorder.length() == 0) return false;
String[] tree = preorder.split(",");
if(tree.length == 1) return tree[0].equals("#");
return dfs(tree) && tree.length == index;
}
int index = 0;
private boolean dfs(String[] tree) {
// start from root
if(index >= tree.length) return false;
if(tree[index].equals("#")) {
index++;
return true;
}
index++;
return dfs(tree) && dfs(tree);
}
}
iteration:
public class Solution {
public boolean isValidSerialization(String preorder) {
if(preorder == null || preorder.length() == 0) return false;
// iteration, add the node
Stack stack = new Stack();
for(String s : preorder.split(",")) {
// check 2 "#"
if(s.equals("#")) {
while(!stack.isEmpty() && stack.peek().equals("#")) {
// pop "#"
stack.pop();
if(stack.isEmpty()) return false;
// pop parent of "#" & "#"
stack.pop();
}
}
stack.push(s);
}
return stack.size() == 1 && stack.peek().equals("#");
}
}
看到discussion還有一種用入度出度的方法，比較厲害，不用額外空間：
除了根節(jié)點(diǎn)和葉子節(jié)點(diǎn)之外，每個(gè)節(jié)點(diǎn)都有2個(gè)出度（left，right）和1個(gè)入度，根節(jié)點(diǎn)非空有2個(gè)出度0個(gè)入度，葉子節(jié)點(diǎn)有1個(gè)入度。令diff = outdegree - indegree，那么從累加diff會(huì)一直保持正，最后為0。從左往右比較好理解，因?yàn)閜reorder總是總root到左再到右，root的diff總是>0的，所以一定是保持positive。從右往左就不知道怎么理解了。。注意diff從1開(kāi)始，因?yàn)閞oot沒(méi)有indegree。
public class Solution {
public boolean isValidSerialization(String preorder) {
int diff = 1;
for(String s : preorder.split(",")) {
if(--diff < 0) return false;
if(!s.equals("#")) diff += 2;
}
return diff == 0;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66598.html
摘要：如果我們從右往左看先序遍歷，就知道后兩個(gè)節(jié)點(diǎn)如果遇到第三個(gè)節(jié)點(diǎn)，則該節(jié)點(diǎn)就應(yīng)當(dāng)是這兩個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)。如果在遍歷的過(guò)程中根節(jié)點(diǎn)數(shù)量小于，則說(shuō)明這棵樹(shù)有問(wèn)題。而如果遍歷結(jié)束之后，剩下的根節(jié)點(diǎn)數(shù)不等于，也說(shuō)明這個(gè)先序遍歷存在問(wèn)題。 題目要求 One way to serialize a binary tree is to use pre-order traversal. When we en...
摘要：如果它是一個(gè)空節(jié)點(diǎn)，我們可以使用一個(gè)標(biāo)記值記錄，例如。例如，上面的二叉樹(shù)可以被序列化為字符串，其中代表一個(gè)空節(jié)點(diǎn)。每個(gè)以逗號(hào)分隔的字符或?yàn)橐粋€(gè)整數(shù)或?yàn)橐粋€(gè)表示指針的。如果滿足前序遍歷，那么最后棧中有且僅有一個(gè)元素，且是。 Description One way to serialize a binary tree is to use pre-order traversal. When ...
摘要：思路理論上說(shuō)所有遍歷的方法都可以。但是為了使和的過(guò)程都盡量最簡(jiǎn)單，是不錯(cuò)的選擇。用作為分隔符，來(lái)表示。復(fù)雜度代碼思路這道題和之前不同，一般的樹(shù)變成了，而且要求是。還是可以用，還是需要分隔符，但是就不需要保存了。 297. Serialize and Deserialize Binary Tree Serialization is the process of converting a...
摘要：如果繼續(xù)降序，說(shuō)明又向左走了，這樣等到下次向右走得時(shí)候也要再次更新最小值。這樣，序列無(wú)效的條件就是違反了這個(gè)最小值的限定。我們同樣可以用本題的方法解，不過(guò)是從數(shù)組的后面向前面遍歷，因?yàn)樵诤竺媪恕５脑鲩L(zhǎng)方向也是從高向低了。 Verify Preorder Sequence in Binary Search Tree Given an array of numbers, verify ...
摘要：題目要求將二叉搜索樹(shù)序列化和反序列化，序列化是指將樹(shù)用字符串的形式表示，反序列化是指將字符串形式的樹(shù)還原成原來(lái)的樣子。假如二叉搜索樹(shù)的節(jié)點(diǎn)較多，該算法將會(huì)占用大量的額外空間。 題目要求 Serialization is the process of converting a data structure or object into a sequence of bits so that...
閱讀 3664·2021-10-12 10:11
閱讀 1026·2021-09-22 15:42
閱讀 3476·2019-08-30 13:06
閱讀 914·2019-08-29 17:05
閱讀 1660·2019-08-29 12:21
閱讀 2388·2019-08-29 11:31
閱讀 1145·2019-08-23 18:37
閱讀 1265·2019-08-23 14:58
