leetcode 331. Verify Preorder Serialization of a Binary Tree 二叉树前序序列验证

布满荆棘的人生 2022-06-07 01:12 106阅读 0赞

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

这道题很简单，就是验证一个给定的序列是否是一个二叉树的前序遍历的序列。

那么我们加入先不考虑最后一个\#号，那么此时数字和\#号的个数应该相同，如果我们初始化一个为0的计数器，遇到数字，计数器加1，遇到\#号，计数器减1，那么到最后计数器应该还是0。下面我们再来看两个返回False的例子，”\#,7,6,9,\#,\#,\#”和”7,2,\#,2,\#,\#,\#,6,\#”，那么通过这两个反例我们可以看出，如果根节点为空的话，后面不能再有节点，而且不能有三个连续的\#号出现。所以我们再加减计数器的时候，如果遇到\#号，且此时计数器已经为0了，再减就成负数了，就直接返回False了，因为正确的序列里，任何一个位置i，在\[0, i\]范围内的\#号数都不大于数字的个数的。当循环完成后，我们检测计数器是否为0的同时还要看看最后一个字符是不是\#号。这个做法参考下面的C++做法

嗯嗯，这个还需要思考，看来编程能力还待提升。

建议和[leetcode 297. Serialize and Deserialize Binary Tree 二叉树的序列化和反序列化][leetcode 297. Serialize and Deserialize Binary Tree] 和 [leetcode 654. Maximum Binary Tree 构造最大二叉树][leetcode 654. Maximum Binary Tree] 一起学习

代码如下：

import java.util.Stack;
    
    public class Solution
    {
        /*
         * using a stack, scan left to right
         * case 1: we see a number, just push it to the stack
         * case 2: we see #, check if the top of stack is also #
         * if so, pop #, pop the number in a while loop, until top of stack is not #
         * if not, push it to stack
         * in the end, check if stack size is 1, and stack top is #
         * */
        public boolean isValidSerialization1(String preorder) 
        {
            if (preorder == null) 
                return false;
            Stack<String> stack = new Stack<>();
            String[] str=preorder.split(",");
            for(int i=0;i<str.length;i++)
            {
                if(str[i].equals("#"))
                {
                    while(stack.isEmpty()==false && stack.peek().equals("#"))
                    {
                        stack.pop();
                        if(stack.isEmpty())
                            return false;
                        stack.pop();
                    }
                    stack.push(str[i]);
                }else 
                    stack.push(str[i]);
            }
            return stack.size()==1 && stack.peek().equals("#");
        }
    
        /*
         * 其实，只是判断节点的位置和数量是否有误，因此不需要栈，也可以操作。
         * 非叶子结点，入度是1，出度是2
         * 叶子节点，入度是1，出度是0
         * 所以计算diff表示总的（入度-出度），初始化1
         * 主要过程中，出现diff<0表示出错，结束后diff==0才可以
         * */
        public boolean isValidSerialization(String preorder) 
        {
            String[] nodes = preorder.split(",");
            int diff = 1;
            for (String node: nodes) 
            {
                diff--;
                if (diff <= -1) 
                    return false;
                if (node.equals("#")==false) 
                    diff += 2;
            }
            return diff == 0;
        }
    }

下面是C++的做法

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        bool isValidSerialization(string preorder)
        {
            stringstream ss(preorder);
            string one;
            vector<string> res;
            while (getline(ss, one, ','))
                res.push_back(one);
    
            int count = 0;
            for (int i = 0; i < res.size() - 1; i++)
            {
                if (res[i] == "#")
                {
                    if (count == 0)
                        return false;
                    count--;
                }
                else
                    count++;
            }
    
            return count == 0 && res.back() == "#";
        }
    
    
        bool isValidSerializationByStack(string preorder) 
        {
            stringstream ss(preorder);
            string one;
            vector<string> skt;
            while (getline(ss, one, ','))
            {
                if (one == "#")
                {
                    while (skt.empty() == false && skt.back() == "#")
                    {
                        skt.pop_back();
                        if (skt.empty() == true)
                            return false;
                        skt.pop_back();
                    }
                    skt.push_back(one);
                }
                else
                    skt.push_back(one);
            }
    
            return skt.size() == 1 && skt.back() == "#";
        }
    };

[leetcode 297. Serialize and Deserialize Binary Tree]: http://blog.csdn.net/jackzhang_123/article/details/78122376
[leetcode 654. Maximum Binary Tree]: http://blog.csdn.net/jackzhang_123/article/details/78865619