My java solution with BFS


  • 0
    C
    	public String serialize(TreeNode root){
    	LinkedList<TreeNode> curLevel = new LinkedList<TreeNode>();
    	Stack<Integer> stack = new Stack<Integer>();
    	if(root == null) return null;
    	stack.push(root.val);
    	curLevel.add(root);
    	while(!curLevel.isEmpty()){
    		LinkedList<TreeNode> nextLevel = new LinkedList<TreeNode>();
    		for(TreeNode node : curLevel){
    			if(node.left != null){
    				nextLevel.add(node.left);
    				stack.push(node.left.val);
    			}else{
    				stack.push(null);
    			}
    			if(node.right != null){
    				nextLevel.add(node.right);
    				stack.push(node.right.val);
    			}else{
    				stack.push(null);
    			}
    		}
    		curLevel = nextLevel;
    	}
    	while(stack.peek() == null){
    		stack.pop();
    	}
    	String ans = stack.toString().replace(" ", "");
    	return ans;
    }
    public TreeNode deserialize(String data){
    	if(data == null)  return null;
    	LinkedList<TreeNode> curLevel = new LinkedList<TreeNode>();
    	data = data.substring(1, data.length()-1);
    	System.out.println(data);
    	String[] str = data.split(",");
    	Queue<Integer> queue = new LinkedList<Integer>();
    	for(int i=0; i<str.length; i++){
    		if(str[i].equals("null"))
    			queue.offer(null);
    		else queue.offer(Integer.valueOf(str[i]));
    	}
    	TreeNode root  = new TreeNode(queue.poll());
    	curLevel.add(root);
    	while(!curLevel.isEmpty()){
    		LinkedList<TreeNode> nextLevel = new LinkedList<TreeNode>();
    		for(TreeNode node : curLevel){
    			if(queue.peek()!= null){
    				TreeNode left = new TreeNode(queue.poll());
    				node.left = left;
    				nextLevel.add(node.left);
    			}else{
    				node.left = null;
    				queue.poll();
    			}
    			if(queue.peek()!= null){
    				TreeNode right = new TreeNode(queue.poll());
    				node.right = right;
    				nextLevel.add(node.right);
    			
    			}else{
    				node.right = null;
    				queue.poll();
    			}
    		}
    		curLevel = nextLevel;
    	}
    	return root;
    }

Log in to reply
 

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