leetcode verify Preorder Serialization of a Binary Tree

题目链接

思路:
动态规划。用一个二维数组记录一下。record[i][j]记录从i到j能不能形成一个树。但是这个方法会超时。

public class Solution {
    public boolean isValidSerialization(String preorder) {
      String[] node=preorder.split(",");
        int n=node.length;
        int[][]record=new int[n][n];
        for(int i=0;i<n;i++)
        {
            record[i][i]=1;
        }
        for(int l=3;l<=n;l++)
        {
            for(int e=n-1;e-(l-1)>=0;e--)
            {
                int s=e-(l-1);
                if(node[s].equals("#"))
                {
                    continue;
                }
                for(int i=s+1;i<e;i++)
                {
                    if(record[s+1][i]==1&&record[i+1][e]==1)
                    {
                        record[s][e]=1;
                        break;
                    }
                }
            }
        }
        return record[0][n-1]==1?true:false;
    }
}

其他人的解法
解法I 利用栈(Stack)数据结构

将元素压入栈

如果当前栈的深度≥3,并且最顶端两个元素为’#’, ‘#’,而第三个元素不为’#’,则将这三个元素弹出栈顶,然后向栈中压入一个’#’,重复此过程

最后判断栈中剩余元素是否只有一个’#’

public class Solution {
    public boolean isValidSerialization(String preorder) {
     String[] node=preorder.split(",");
        int n=node.length;
        LinkedList<String> stack=new LinkedList<String>();
        for(int i=0;i<n;i++)
        {
            stack.add(node[i]);
            int size=stack.size();
            while(size>=3&&stack.get(size-1).equals("#")&&stack.get(size-2).equals("#")&&!stack.get(size-3).equals("#"))
            {
                stack.pollLast();
                stack.pollLast();
                stack.pollLast();
                stack.add("#");
                size=stack.size();
            }
        }
        return stack.size()==1&&stack.pollLast().equals("#");
    }
}
相关文章
相关标签/搜索