Java PreOrder and Stack Solution


  • 0
    M
    /**
     * 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 null;
            
            StringBuilder sb = new StringBuilder();
            preOrder(root, sb);
            
            return sb.toString();
        }
        
        private void preOrder(TreeNode root, StringBuilder sb) {
            if (root == null) {
                sb.append("#!");
                return;
            }
            
            sb.append(root.val + "!");
            
            preOrder(root.left, sb);
            preOrder(root.right, sb);
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data == null || "#!".equals(data))
                return null;
            
            String[] ds = data.split("!");
            
            TreeNode root =  new TreeNode(Integer.valueOf(ds[0]));
            Stack<TreeNode> stack = new Stack<TreeNode>();
            stack.push(root);
            
            boolean isRight = false;
            for (int i = 1; i < ds.length; i++) {
                if ("#".equals(ds[i])) {
                    if (isRight) {
                        stack.pop();
                    } else {
                        isRight = true;
                    }
                } else {
                    TreeNode node = new TreeNode(Integer.valueOf(ds[i]));
                    if (isRight) {
                        stack.pop().right = node;
                    } else {
                        stack.peek().left = node;
                    }
                    stack.push(node);
                    
                    if (isRight) {
                        isRight = false;
                    }
                }
            }
            
            return root;
        }
    }
    
    // Your Codec object will be instantiated and called as such:
    // Codec codec = new Codec();
    // codec.deserialize(codec.serialize(root));
    

Log in to reply
 

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