Java BFS solution easy to understand, serialize/deserialize runtime O(n)


  • 0
    K

    Inspired by solution https://discuss.leetcode.com/topic/22848/ac-java-solution/26.

    Each tree node can be represented by "val/num/", where val is the value of the node and num indicate his children situation (num == 3 meaning having two children, num == 2 meaning having only left child, num == 1 meaning having only right child, num == 0 meaning having no child).

    The time complexity for both serialize and deserialize is O(n), where n is the number of nodes in BST. The trade-off here is that I use an extra char "num" as in val/num/.

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Codec {
    
        // Encodes a tree to a single string.
    	public String serialize(TreeNode root) {
            if (root == null) return "";
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            StringBuilder sb = new StringBuilder();
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                int num = 0;
                if (node.left != null && node.right != null) {
                    // 3 indicates having both left and right child
                    num = 3;
                    queue.offer(node.left);
                    queue.offer(node.right);
                } else if (node.left != null) {
                    // 2 indicates having left child
                    num = 2;
                    queue.offer(node.left);
                } else if (node.right != null) {
                    // 1 indicates having right child
                    num = 1;
                    queue.offer(node.right);
                } // 0 indicates having no child
                
                sb.append(node.val).append("/").append(num).append("/");
            }
            return sb.toString();
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data == null || data.length() < 4) return null;
            char[] text = data.toCharArray();
            int i = 0;
            TreeNode root = new TreeNode(-1);
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                // Set node value
                i = readNode(text, i, node);
                // Read node's child number
                int num = 0;
                while (text[i] != '/') {
                    num = num*10 + Character.getNumericValue(text[i]);
                    i++;
                }
                i++;
                if (num == 3) {
                    addLeftNode(node, queue);
                    addRightNode(node, queue);
                } else if (num == 2) {
                    addLeftNode(node, queue);
                } else if (num == 1) {
                    addRightNode(node, queue);
                }
            }
            return root;
        }
        
        private int readNode(char[] text, int i, TreeNode node) {
            int val = 0;
            while (text[i] != '/') {
                val = val*10 + Character.getNumericValue(text[i]);
                i++;
            }
            node.val = val;
            return i+1;
        }
        
        private void addLeftNode(TreeNode parent, Queue<TreeNode> queue) {
            TreeNode node = new TreeNode(-1);
            parent.left = node;
            queue.offer(node);
        }
        
        private void addRightNode(TreeNode parent, Queue<TreeNode> queue) {
            TreeNode node = new TreeNode(-1);
            parent.right = node;
            queue.offer(node);
        }
    }
    
    // Your Codec object will be instantiated and called as such:
    // Codec codec = new Codec();
    // codec.deserialize(codec.serialize(root));
    

  • -1
    K

    May I ask if the following two BST represent the same data structure in the leetcode test. Because the preorder traversal of these two instance have the same result.

      1
    2  3 balanced
    
      1
        2
          3 not-balanced
    

  • 0
    M

    @keweishang the first example is not a BST


Log in to reply
 

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