Easy java recursive solution, just follow what preorder does


  • 1
    K

    Version 2: without global variable:

    public class Solution {
    	public boolean isValidSerialization(String preorder) {
    		int[] pos = new int[]{-1};
    		String[] s = preorder.split(",");
    		return isValid(s, pos) && pos[0] == s.length - 1;
        }
    	private boolean isValid(String[] s, int[] pos){
            if (++pos[0]>= s.length) return false;
            if (s[pos[0]].equals("#")) return true;        	
    		//verify left and right node
            return isValid(s, pos) && isValid(s, pos);
    	}
    }
    

    Original version below:

    The idea is to verify the root, the left and right. I am still learning java, let me know if this can be improved.

    public class Solution {
    	int pos = -1;
    	public boolean isValidSerialization(String preorder) {
    		String[] s = preorder.split(",");
    		return isValid(s) && pos == s.length - 1;
        }
    	private boolean isValid(String[] s){
            if (++pos >= s.length) return false;
            if (s[pos].equals("#")) return true;
    		//verify left and right node
            return isValid(s) && isValid(s);
    	}
    }

  • 0
    B

    This seems like a reasonable thing to do. It is very similar to my own algorithm. The only critique for improvement would be to avoid using a member variable to store your index. Depending on the interviewer or the situation this could be frowned upon since it is considered poor style to use member variables that don't represent an object's state. Instead, you could just pass in the index and return it from your recursive function instead of a boolean. Then you could just check the length of s against the returned index value. At the very least, make all member variables private.


  • 0
    L

    The same idea with you but I don't use private variable.

    public class Solution {
        public boolean isValidSerialization(String preorder) {
            String[] strings = preorder.split(",");
            return check(strings, 0) == strings.length-1;
        }
    
        private int check(String[] strings, int pos) {
            if (pos == -1 || pos >= strings.length) return -1;
            if (strings[pos].equals("#")) return pos;
            int left = pos >= 0? check(strings, pos+1):-1;
            int right = left >= 0? check(strings, left+1):-1;
            return right;
        }
    }

  • 0
    K

    Thanks. I have updated the code using a size one array to track the position.


Log in to reply
 

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