Java solution using dfs


  • 0
    C
    public boolean isValidSerialization(String preorder) {
            if(preorder.length() == 1 && preorder.charAt(0) == '#'){
                return true;
            }
            
            if(preorder.length() > 1 && preorder.charAt(0) == '#'){
                return false;
            }
            
            String[] strArr = preorder.split(",");
    		Stack<int[]> stack = new Stack<int[]>();
    
    		int idx = 0;
    		stack.push(new int[] { 0, Integer.valueOf(strArr[idx++])});
    		while (idx < strArr.length) {
    			if (stack.isEmpty()) {
    				return false;
    			} else if (stack.peek()[0] == 1) {
    				stack.pop();
    			} else {
    				stack.peek()[0] = 1;
    			}
    
    			if (!strArr[idx].equals("#")) {
    				stack.push(new int[] { 0 , Integer.valueOf(strArr[idx])});
    			}
    			idx++;
    		}
    		
    		return stack.isEmpty();
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.