leetcode解题: Verify Preorder Serialization of a Binary Tree (331)

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：剪叶子的思路

每当遇到两个连续的”#”的时候,并且前一个字符不是”#”的时候,可以判断这是一个叶子.如果我们把每一个叶子剪掉并且替换成”#”的话,我们实际上在不停的从下往上的砍叶子直到砍完为止.
这样的思路对于binary tree在其他题目中似乎也见过.那么对于一个valid的binary tree,最后一定是能砍光的. 以此可以得出如下的算法.
C++
注意的是这里用vector当成一个stack用,因为我们需要access前面的2个元素,用vector效率较高.

class Solution {
public:
    bool isValidSerialization(string preorder) {
        std::istringstream ss(preorder);
        vector<string> s;
        string item;
        while (getline(ss, item, ',')) {
            s.push_back(item);
            while (s.size() >= 3 && item == "#" && s[s.size() - 2] == "#" && s[s.size() -3] != "#") {
                s.pop_back();
                s.pop_back();
                s.pop_back();
                s.push_back(item);
            }
        }
        return s.size() == 1 && s[0] == "#";
    }
};

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

解法2: outbound - inbound

这个解法的核心是. 首先把所有的NULL NODE看成是valid node. 每一个node的inbound/outbound的connection可以统计如下:

每一个非NULL节点都有两个outbound和一个inbound (除了root)
每一个NULL节点都有一个inbound和0个outbound

一个valid的树如果计算所有的outbound和inbound的差,一定是等于0的,并且从root到任意一节点, outbound - inbound都一定不是负数.
有了这个结论之后, code写起来很直白.
C++

lang: cpp

class Solution {
public:
    bool isValidSerialization(string preorder) {
        std::istringstream ss(preorder);
        string item;
        int diff = 1;
        while (getline(ss, item, ',')) {
            if (--diff < 0) return false;
            if (item != "#") diff += 2;
        }
        return diff == 0;
    }
};

class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] nodes = preorder.split(",");
        int diff = 1;   // calculate outdegree - indegree
        for (int i = 0; i < nodes.length; i++) {
            diff--;
            if (diff < 0) return false;
            if (!nodes[i].equals("#")) diff += 2;
        }
        return diff == 0;
    }
}

解法1： 剪叶子的思路

解法2: outbound - inbound

解法1：剪叶子的思路