Java solution using stack, not filling with #/null, beats 94%


  • 1
    F

    Figured since most other people were doing something similar to how LeetCode serializes trees, I would try something different. Code is pretty easy to understand, but basically I use [ ] to enclose left children and ( ) to enclose right children. Therefore this approach doesn't require filling in null nodes. De-serializing becomes a simple stack solution, popping and pushing when we get to a bracket/paren.

    public class Codec {
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            StringBuilder str = new StringBuilder();
            serialize(root, str);
            return str.toString();
        }
        
        private void serialize(TreeNode node, StringBuilder str)
        {
            if (node == null) return;
            
            // add current node
            str.append(node.val);
            
            // add left node
            if (node.left != null)
            {
                str.append("[");
                serialize(node.left, str);
                str.append("]");
            }
            
            // add right node
            if (node.right != null)
            {
                str.append("(");
                serialize(node.right, str);
                str.append(")");
            }
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data)
        {
            if (data == null || data.length() <= 0) return null;
            
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode current = new TreeNode(0);
            int sign = 1;
            
            for (int i = 0; i < data.length(); i++)
            {
                char c = data.charAt(i);
                if (Character.isDigit(c))
                {
                    // add to the current value
                    current.val = (current.val * 10) + (c - '0');
                }
                else if (c == '-')
                {
                    sign = -1;
                }
                else if (c == '[' || c == '(')
                {
                    // correct sign of final current value
                    current.val *= sign;
                    sign = 1;
                    
                    // push current value onto stack and create new current node
                    stack.push(current);
                    current = new TreeNode(0);
                }
                else if (c == ']' || c == ')')
                {
                    // correct sign of final current value
                    current.val *= sign;
                    sign = 1;
                    
                    // pop of top of stack and add current item as a child
                    TreeNode top = stack.pop();
                    
                    if (c == ']')
                        top.left = current;
                    else
                        top.right = current;
                    
                    // set current to the top and continue
                    current = top;
                }
            }
            
            return current;
        }
    }
    

Log in to reply
 

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