Verify Preorder Serialization of a Binary Tree

2016-05-26

问题描述

给定一个二叉树的前序遍历序列（preorder），由这个给定的序列推测原二叉树是否存在。#表示NULL。

Example 1

给定序列："9,3,4,#,#,1,#,#,2,#,6,#,#"，则可构造如下的二叉树：

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

所以返回True;

Example 2

给定序列"9,#,#,1", 则不存在这样一颗二叉树。

思路

解法一：

用一个栈来模拟树的遍历过程。
我采用一个int为元素的栈，如果遇到非#，则压入一个2，当遇到#时，栈顶元素减一，当栈顶为0时，弹出栈顶，弹出后下一个栈顶也要进行减一的操作，以此类推上述的操作。需要注意的是：

当栈为空，而且需要压入的也不是树的第一个元素，则返回false。

当整个过程结束后，判断栈是否为空，空则返回true，反之false。

算法的时间复杂度是\(\Theta(N)\),空间复杂度也是\(\Theta(N)\)。

解法二：

利用一个树容量的概念来巧妙求解。起初树的容量为1，因为只允许放一个根节点。当加入一个节点，树的容量减一，当这个节点不是#节点，树的容量再加2。过程中如果出现容量等于0的情况，则返回false。整个过程结束后，判断容量是否为0，是则返回true反之false。

算法的时间复杂度是\(\Theta(N)\),而空间复杂度降到\(\Theta(1)\)。

Code

解法一：

bool isValidSerialization(string preorder) {
        if (preorder == "#") return true;
        stack<int> s;
        int i, start;
        string s1 = "";
        int tmp;
        for (start = 0, i = 0; i < preorder.size(); ){
            while(i < preorder.size() && preorder[i] != ',') i++;
            s1 = preorder.substr(start, i - start);
            
            if (s1 != "#"){
                if (start != 0 && s.empty()) return false;
                s.push(2);
            }
            else{
                if (s.empty()) return false;
                s.top()--;
                while (!s.empty() && s.top() == 0) {
                    s.pop();
                    if (!s.empty())
                    s.top()--;
                }
            }
            
            start = ++i;
            
        }
        
        
        return s.empty();
}

解法二：

bool isValidSerialization(string preorder) {
    if (preorder.empty()) return false;
    
    preorder += ',';
    int sz=preorder.size();
    int idx = 0;
    int capacity=1;
    for (idx=0;idx<sz;idx++){
        if (preorder[idx] != ',') continue;
        capacity--;
        if (capacity < 0) return false;
        if (preorder[idx-1] != '#') capacity += 2;
    }
    return capacity==0;
}