LeetCode Verify Preorder Serialization of a Binary Tree

· 293 words · 2 minute read
2017年6月
LeetCode

331. Verify Preorder Serialization of a Binary Tree

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

方法

方法1

对于树的遍历，除了递归也可以用栈，所以，看到用字符串表示的树的序列，一定要想到栈！！！

总结一下何时会使用到栈：

包含有先进后出逻辑的，考虑用栈。 如递归，树的遍历，一些字符串的遍历

回到题目，具体方法如下：

1. 创建栈，对于字符串从左往右扫描
2. 观察当前扫描的字符串，
   若为数，则直接push到栈中。
   若为`#`，观察栈顶是否也为`#`，若是，则循环pop `#`和栈顶`#`的下一个元素，直到栈顶不为`#`，然后再push`#`到栈中。
3. 若最后栈的大小为1且栈中的元素为`#`，则先序序列正确。

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

方法2

若先序序列正确，则可以生成一个先序序列为该先序序列的树，由树可以想到树的出度和入度之和为0。

  • 所有非空节点提供2个出度和一个入度，根节点除外。
  • 所有空节点提供0个出度和一个入度

即满足 diff = outdegree - indegree, diff = 0 时，该先序序列正确

public boolean isValidSerialization(String preorder) {
    String[] nodes = preorder.split(",");
    int diff = 1;
    for (String node: nodes) {
        if (--diff < 0) return false;
        if (!node.equals("#")) diff += 2;
    }
    return diff == 0;
}
Share