This is the 8th day of my participation in the More text Challenge. For details, see more text Challenge

Leetcode sword refers to offer37- Serialized binary tree

[Blog link]

The way to study 🐔

The nuggets home page

[Topic]

Implement two functions to serialize and deserialize the binary tree. You need to design an algorithm to serialize and deserialize the binary tree. There is no logic for your sequence/deserialization algorithm to perform, you just need to ensure that a binary tree can be serialized to a string and deserialize the string to the original tree structure. Tip: The input and output formats are the same as the ones currently used by LeetCode, see LeetCode Serialized binary tree format for details. You don't have to take this approach, you can take other approaches to the problem. Example: Enter: root = [1.2.3.null.null.4.5] Output: [1.2.3.null.null.4.5[c]. [D]297The same question: HTTPS://leetcode-cn.com/problems/serialize-and-deserialize-bInary -tree/ Related Topics tree depth first search breadth first search design string binary tree 👍178 👎 0

Copy the code

[Topic link]

Leetcode title link

[making address]

Code link

[思路介绍]

Idea 1: BFS breadth-first search, then deserialization, the overall problem difficulty may be code implementation rather than thinking logic

public class Codec {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            String serialization = "";
            //corner case
            if (root == null) {
                return serialization;
            }
            Deque<TreeNode> deque = new LinkedList<>();
            deque.add(root);
            while(! deque.isEmpty()) { TreeNode temp = deque.poll();if (temp == null) {
                    serialization += "null,";
                    continue;
                }
                serialization += (temp.val + ",");
                deque.add(temp.left);
                deque.add(temp.right);
            }
            return serialization.substring(0, serialization.length() - 1);
        }

        // Decodes your encoded data to tree.
        // Backtrace the tree node from the BFS result
        public TreeNode deserialize(String data) {
            //corner case
            if ("".equals(data)){
                return null;
            }
            String[] trees = data.split(",");
            if (trees.length == 1) {
                return new TreeNode(Integer.parseInt(data));
            }
            TreeNode root = new TreeNode(Integer.parseInt(trees[0]));
            TreeNode cur = root;
            Deque<TreeNode> deque = new LinkedList<>();
            deque.add(root);
            int step = 1;
            while(! deque.isEmpty() && step < trees.length) { TreeNode temp = deque.poll();if ("null".equals(trees[step])){
                    temp.left = null;
                }else{
                    temp.left = new TreeNode(Integer.parseInt(trees[step]));
                    deque.add(temp.left);
                }
                step++;
                if (step == trees.length){
                    return root;
                }
                if ("null".equals(trees[step])){
                    temp.right = null;
                }else{
                    temp.right = new TreeNode(Integer.parseInt(trees[step]));
                    deque.add(temp.right);
                }
                step++;
            }
            returncur; }}Copy the code

Time complexity O(n)

---

Idea 2: DFS

• The same idea is that the difficulty may be more in the code implementation

public class Codec {
        String serialization = "";
        int i = 0;
        public String serialize(TreeNode root) {
            dfs(root);
            return serialization.substring(0, serialization.length() - 1);
        }

        public TreeNode deserialize(String data) {
            //corner case
            if ("".equals(data)) {
                return null;
            }
            String[] trees = data.split(",");
            if ("null".equals(trees[0])){
                return null;
            }
            TreeNode root = new TreeNode(Integer.parseInt(trees[0]));
            i++;
            deserializeDfs(root, trees);
            return root;
        }

        public void deserializeDfs(TreeNode root, String[] trees) {
            int n = trees.length;
            if (i == n) {
                return;
            }
            if ("null".equals(trees[i])) {
                root.left = null;
                i++;
            } else {
                root.left = new TreeNode(Integer.parseInt(trees[i]));
                i++;
                deserializeDfs(root.left, trees);
            }
            if (i == n) {
                return;
            }
            if ("null".equals(trees[i])){
                root.right = null;
                i++;
            }else{
                root.right = newTreeNode(Integer.parseInt(trees[i])); i++; deserializeDfs(root.right, trees); }}public void dfs(TreeNode root) {
            if (root == null) {
                serialization += "null,";
                return;
            }
            serialization += (root.val + ",");
            if (root.left == null) {
                serialization += "null,";
            }else{
                dfs(root.left);
            }
            if (root.right == null){
                serialization += "null,";
            }else{ dfs(root.right); }}}Copy the code

** Time complexity O(n) **