首页 > 代码库 > [LeetCode] 331. Verify Preorder Serialization of a Binary Tree Java
[LeetCode] 331. Verify Preorder Serialization of a Binary Tree Java
题目:
One way to serialize a binary tree is to use pre-order 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 #
.
_9_ / 3 2 / \ / 4 1 # 6 / \ / \ / # # # # # #
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, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.
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"
.
Example 1:"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true
Example 2:"1,#"
Return false
Example 3:"9,#,#,1"
Return false
题意及分析:给出一个二叉树的前序遍历,要求判断该二叉树是否合法。
第一种方法:观察可以得知,每一个叶节点的结构是“数字,#,#”,所以我们把所有的这样的格式都替换成一个“#”,不断地收缩,直到缩到最后应该是一个#。代码如下:
public class Solution { public boolean isValidSerialization(String preorder) { String[] strings=preorder.split(","); boolean res=false; List<String> list=new ArrayList<>(); //每一个叶节点的结构是“数字,#,#”,所以我们把所有的这样的格式都替换成一个“#”,不断地收缩,直到缩到最后应该是一个# for(int i=0;i<strings.length;i++){ String str = strings[i]; list.add(str); //收缩 while(list.size()>=3&&list.get(list.size()-1).equals("#")&&list.get(list.size()-2).equals("#")&&!list.get(list.size()-3).equals("#")){ list.remove(list.size()-1); list.remove(list.size()-1); list.remove(list.size()-1); list.add("#"); } } if(list.size()==1&&list.get(0).equals("#")) res = true; // System.out.println(res); return res; } }
第二种方法:
在构建的过程中,记录出度与入度之差,记为diff = outdegree - indegree
当遍历节点时,我们令diff - 1(因为节点提供了一个入度)。如果diff<0,返回false;如果节点非空,再令diff + 2(因为节点提供了2个出度)。
最后判断diff==0;
理解:如果在遍历过程中的某时刻,系统的入度>出度,则说明当前序列中出现过的所有分支节点的“空闲分支”均已用完,后序节点没有办法挂载到之前出现的节点之上,从而判定先序遍历的序列是不合法的。
代码如下:
public boolean isValidSerialization(String preorder) { String[] res = preorder.split(","); int diff = 1; for (String each : res) { if (--diff < 0) { return false; } if (!"#".equals(each)) { diff += 2; } } return diff == 0; }
[LeetCode] 331. Verify Preorder Serialization of a Binary Tree Java