Share my Java iterative preorder solution


  • 1

    As we know, LeetCode uses Level Order Traversal to encode and decode binary tree, we can also use Preorder Traversal to do the same thing.

    Following is the Java iterative solution, time complexity for both encoding and decoding is O(n).

    In my decoding solution, I use split() to store the values in list[], we can also use two pointers to get each component separated by the comma, that will make the space complexity down to O(h) where h is the height of the tree.

    public class Codec {
    
      // Encodes a tree to a single string.
      public String serialize(TreeNode root) {
        if (root == null) return null;
        
        String delim = "";
        StringBuilder sb = new StringBuilder();
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        // preorder traversal
        while (!stack.isEmpty()) {
          TreeNode node = stack.pop();
          sb.append(delim).append(node == null ? "#" : String.valueOf(node.val));
          delim = ",";
          
          if (node != null) {
            stack.push(node.right);
            stack.push(node.left);
          }
        }
        
        return sb.toString();
      }
      
      // Decodes your encoded data to tree.
      public TreeNode deserialize(String data) {
        if (data == null) return null;
        
        String[] list = data.split(",");
        
        // create the root node and push it to the stack
        TreeNode root = new TreeNode(Integer.valueOf(list[0]));
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        // direction flag
        boolean left = true;
        
        for (int i = 1; i < list.length; i++) {
          TreeNode node = list[i].equals("#") ? null : new TreeNode(Integer.valueOf(list[i]));
          
          if (left) {
            stack.peek().left = node;
            if (node == null) left = false;
          } else {
            stack.pop().right = node;
            if (node != null) left = true;
          }
          
          if (node != null) stack.push(node);
        }
        
        return root;
      }
        
    }

Log in to reply
 

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