Easy way to reconstruct BST without stack or queue


  • 0
    B
    public class Codec {
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if(root == null){
                return "";
            }
            StringBuilder sb = new StringBuilder();
            preOrder(root, sb);
            return sb.deleteCharAt(sb.length()-1).toString();
        }
        public void preOrder(TreeNode root, StringBuilder sb){
            if(root == null){
                return;
            }
            sb.append(root.val).append(",");
            preOrder(root.left, sb);
            preOrder(root.right, sb);
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if(data == null || data.length() == 0){
                return null;
            }
            String[]s = data.split(",");
            int []nums = new int [s.length];
            for(int i = 0; i < s.length; i++){
                nums[i] = Integer.parseInt(s[i]);
            }
            return build(nums,0,s.length-1); 
        }
        public TreeNode build(int[] nums, int start, int end){
            if(start > end){
                return null;
            }
            if(start == end){
                return new TreeNode(nums[start]);
            }
            int p = start;
            for(;p <= end; p++){
                if(nums[p] > nums[start]){
                    break;
                }
            }
            TreeNode root = new TreeNode(nums[start]);
            root.left = build(nums,start + 1, p - 1); 
            root.right = build(nums,p, end); 
            return root;
        }
    }
    

Log in to reply
 

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