Java recursion solution


  • 10
    I

    Main idea is checking balance of nodes from bottom-up manner and bubble up failure condition.

    public class Solution {
    	public boolean isValidSerialization(String preorder) {
    		String[] tree = preorder.split(",");
    		return valid(tree, 0) == tree.length-1;
    	}
    
    	private int valid(String[] tree, int current) {
    		if(current >= tree.length) return -1;
    		if("#".equals(tree[current])) return current;
    
    		// left
    		int next = valid(tree, current + 1);
    		if(next == -1) return -1;
    
    		// right
    		next = valid(tree, next + 1);
    		return next == -1 ? -1 : next;
    	}
    }

  • 2
    V

    A similar solution:

    public boolean isValidSerialization(String preorder) {
        String[] strs = preorder.split(",");
        return helper(strs, 0) == strs.length;
    }
    
    private int helper(String[] strs, int i) {
        if (i < 0 || i == strs.length)
            return -1;
        if (strs[i].equals("#"))
            return i+1;
        return helper(strs, helper(strs, i+1));
    }

  • 0

    A very interesting solution.
    Compared to stack version and in/out degree version. I enjoy this one most.


  • 0
    F

    I wrote the similar solution:

    public boolean isValidSerialization(String preorder) {
    	String[] cs = preorder.split(",");
    	int index = helper(cs, 0);
    	return index == cs.length - 1;
    }
    
    private int helper(String[] preorder, int index) {
    	if (index >= preorder.length)
    		return index;
    	if (preorder[index].equals("#"))
    		return index;
    	int left = helper(preorder, index + 1);
    	if (left >= preorder.length)
    		return left;
    	int right = helper(preorder, left + 1);
    	return right;
    }

  • 0
    X

    I have the same idea with you.
    See my post here for more explanation.

    Code in C++

    class Solution {
    public:
        bool isValidSerialization(string preorder) {
            stringstream ss(preorder);
    
            // two conditions are required:
            // 1. not too short
            // 2. not too long
            return notTooShort(ss) && ss.eof() == true;
        }
    private:
        bool notTooShort(stringstream &ss) {
            string val_str;
            getline(ss, val_str, ',');
    
            // too short
            if (val_str.empty()) {
                return false;
            }
    
            if (val_str == "#") {
                return true;
            }
    
            // not too short for both left and right child
            return notTooShort(ss) && notTooShort(ss);
        }
    };
    

  • 0
    C

    I wrote a similar one:

        public boolean isValidSerialization(String preorder) {
            String[] nodes = preorder.split(",");
            
            return helpValidSerialization(nodes, 0) == nodes.length;
            
        }
        
        private int helpValidSerialization(String[] nodes, int curr){
            if(curr >= nodes.length) return -1;
            
            if(nodes[curr].equals("#")){
                return curr+1;
            }
            
            int left = helpValidSerialization(nodes, curr+1);
            if(left == -1) return -1;
            int right = helpValidSerialization(nodes, left);
            if(right == -1) return -1;
            
            return right;
        }
    

Log in to reply
 

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