笔试算法题记录1

判断给定的前序遍历序列能否构成合法的二叉树

#带表空节点，如3## 表示根节点是3，左子树和右子树都是空的。这题关键是考虑空节点的情况。将合法的左子树和右子树变为空节点再这样递归考虑，最后只剩一个#时即为合法情况，需要注意的是如果#入栈后栈中出现了连续3个#号的话，则表明 字符串非法。

import java.util.Scanner;
import java.util.Stack;

public class Main{
    /*
    使用栈结构，从左往右扫描字符串序列，入栈
    如果栈顶是数字，则继续入栈
    如果栈顶是#号，此时入栈的是#,那么出栈3位，入栈一位#
    如果栈顶是#号，此时入栈的是数字，不管它，继续入栈
    最后栈中应该只剩一个#号，需要注意的是如果#入栈后栈中出现了连续3个#号的话，则表明字符串非法
    */
    public static boolean pushCharp(Stack<Character> sk){
        boolean flag=true;
        /*栈长度大于2且栈顶元素是#*/
        if(sk.size()>=2&&sk.peek()=='#'){
            char a=sk.pop();
            char b=sk.pop();
            if(b=='#'){
                flag=false;
            }else{
                /*这里需要递归判断，因为出栈3位，入栈一位#又是相似的判断情况*/
                pushCharp(sk);
            }
        }
        /*长度不足2, 或者栈顶是数字，那么#直接入栈*/
        else{
            sk.push('#');
        }
        return flag;
    }
    
    public static boolean isValidation(String s){
        //将字符串变为字符数组,字符串的toCharArray方法
        char[] ss=s.toCharArray();
        //java中栈Stack的用法
        Stack<Character> sk=new Stack<Character>();
        for(char c:ss){
            /*如果要入栈的是#,需单独处理*/
            if(c=='#'){
                if(!pushCharp(sk)){
                    return false;
                }
            }
            /*数字的话直接入栈即可*/
            else{
                sk.push(c);
            }
        }
        /*判断最后栈中是不是只剩一个#号*/
        if(sk.size()==1&&sk.peek()=='#')
            return true;
        return false;
    }
    
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String s=sc.next();
        if(isValidation(s)){
            System.out.println("合法....");
        }else{
            System.out.println("不合法....");
        }
    }
}

 测试了几组数据，都通过了，但是因为没有平台提供的测试数据所以不知道能否完全通过。