My accepted java recursion solution


  • 0
    A

    public class Solution {
    static class Tuple {
    boolean isTree;
    int end;
    Tuple(boolean isTree, int end) { this.isTree = isTree; this.end = end;}
    }
    public boolean isValidSerialization(String preorder) {
    Tuple end = helper(preorder, 0);
    return end.isTree && (end.end == preorder.length() -1);
    }

    Tuple helper(String str, int n) {
    	if(n >= str.length()) return new Tuple(false, -1); //this hsouldn't happen
    	char c = str.charAt(n);
    	if(c == '#') return new Tuple(true, n);
    
    	Tuple left = helper(str, next(str, n)) ;
    	if(!left.isTree) return new Tuple(false, -1);
    	Tuple right = helper(str, next(str, left.end));
    	if(!right.isTree) return new Tuple(false, -1);
    	return new Tuple(true, right.end);
    }
    int next(String str, int i) {
    	for(; i < str.length() && str.charAt(i) != ','; i++);
    	return i+1;
    }
    

    }


Log in to reply
 

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