Shortest and Clear Java Solution


  • 0
    public class Codec {
        public String serialize(TreeNode root) {
            if(root == null) return "";
    
            Deque<TreeNode> stack = new LinkedList<>();
            StringBuilder sb = new StringBuilder();
            stack.offerLast(root);
            //preorder
            while(!stack.isEmpty()){
                TreeNode poll = stack.pollLast();
                sb.append(poll.val).append("/");
                if(poll.right != null){
                    stack.offerLast(poll.right);
                }
                if(poll.left != null){
                    stack.offerLast(poll.left);
                }
            }
            return sb.toString();
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if(data == null || data.length() == 0) return null;
    
            String[] nums = data.split("/");
            return getNode(nums, 0, nums.length - 1);
        }
    
        private TreeNode getNode(String[] array, int i, int j){
            //corner case 
            if(i > j) return null;
            int cur = Integer.valueOf(array[i]);
            TreeNode root = new TreeNode(cur);
            if(i == j) return root;
    
            //k is the beginning index of right subtree
            int k = i+1;
            for(; k <= j; k++){
                if(Integer.valueOf(array[k]) > cur) break;
            }
            //connect the children
            root.left = getNode(array, i+1, k-1);
            root.right = getNode(array, k, j);
    
            return root;
        }
    }
    

Log in to reply
 

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