树的序列化、反序列化【前序、后序、层序】及常见树的题目

客官°小女子只卖身不卖艺 2024-04-08 09:20 49阅读 0赞

## 一、树的序列化、反序列化【前序、后序、层序】 ##

> 在实际开发过程中，一些特殊的数据结构无法用普通的数据类型表示出来，我们需要将其序列化，然后在我们需要使用的时候再反序列化

二叉树节点结构：

//二叉树节点结构
    public static class Node {
        
        public int value;
        public Node left;
        public Node right;
    
        public Node(int data) {
        
            this.value = data;
        }
    }

### 1 树的前序：序列化与反序列化 ###

#### 1.1 树的序列化【前序】 ####

//先序序列化
    public static Queue<String> preSerial(Node head){
        
        Queue<String> ans = new LinkedList<>();
        pres(head, ans);
        return ans;
    }
    
    public static void pres(Node head, Queue<String> ans){
        
        //如果head（节点）为null,也需要添加进去，占位
        if(head == null){
        
            ans.add(null);
        } else {
        
            ans.add(String.valueOf(head.value));
            pres(head.left, ans);
            pres(head.right, ans);
        }
    }

#### 1.2 树的反序列化【前序】 ####

public static Node buildByPreQueue(Queue<String> preList){
        
        if(preList == null || preList.size() == 0){
        
            return null;
        }
        return preb(preList);
    }
    
    public static Node preb(Queue<String> preList){
        
        //出队列
        String value = preList.poll();
        //判断弹出是否为null
        if(value == null){
        
            return null;
        }
        Node head = new Node(Integer.valueOf(value));
        //队列中：中左右 【出：中左右，先进先出】
        head.left = preb(preList);
        head.right = preb(preList);
        return head;
    }

### 2 树的后序：序列化、反序列化 ###

> 注意：树无法使用中序来进行序列化、反序列化【会产生歧义】

#### 2.1 树的序列化【后序】 ####

//后序列化【左右根】
    public static Queue<String> posSerial(Node head){
        
        Queue<String> queue = new LinkedList<>();
        poss(queue, head);
        return queue;
    }
    public static void poss(Queue<String> queue, Node head){
        
        //为null也需要添加：需要占位
        if(head == null){
        
            queue.add(null);
            return;
        }
        poss(queue, head.left);
        poss(queue, head.right);
        queue.add(String.valueOf(head.value));
    }

#### 2.2 树的反序列化【后序】 ####

public static Node buildByPosQueue(Queue<String> posList){
        
         if(posList == null || posList.size() == 0){
        
             return null;
         }
         //后序【左右根】
         //利用栈结构，构建根右左
         Stack<String> stack = new Stack<>();
         while (!posList.isEmpty()){
        
             stack.push(posList.poll());
         }
         return posb(stack);
     }
    
     public static Node posb(Stack<String> posstack){
        
         String value = posstack.pop();
         if(value == null){
        
             return null;
         }
         //根 右 左
         Node head = new Node(Integer.parseInt(value));
         head.right = posb(posstack);
         head.left = posb(posstack);
         return head;
     }

### 3 树的层序：序列化、反序列化 ###

#### 3.1 序列化【层序】 ####

//层序：序列化
    public static Queue<String> levelSerial(Node head){
        
        Queue<String> ans = new LinkedList<>();
        if(head == null){
        
            ans.add(null);
        } else {
        
            ans.add(String.valueOf(head.value));
            Queue<Node> queue = new LinkedList<>();
            queue.add(head);
            while(!queue.isEmpty()){
        
                //每次找到新的节点
                head = queue.poll();
                if(head.left != null){
        
                    //左不为null，进队列
                    ans.add(String.valueOf(head.left.value));
                    queue.add(head.left);
                } else {
        
                    ans.add(null);
                }
                if(head.right != null){
        
                    ans.add(String.valueOf(head.right.value));
                    queue.add(head.right);
                } else {
        
                    ans.add(null);
                }
            }
        }
        return ans;
    }

#### 3.2 反序列化【层序】 ####

思路：  
先弹出一个head，然后将head放入队列，判断head是否为null，如果不为null，从levelList中弹出左右节点，并且将其左右节点添加进queue

//层序：反序列化
    public static Node buildByLevelQueue(Queue<String> levelList){
        
         if(levelList == null || levelList.size() == 0){
        
             return null;
         }
         //先弹出head节点
         Node head = generateNode(levelList.poll());
         Queue<Node> queue = new LinkedList<>();
         if(head != null){
        
             queue.add(head);
         }
         Node node = null;
         while(!queue.isEmpty()){
        
             node = queue.poll();
             node.left = generateNode(levelList.poll());
             node.right = generateNode(levelList.poll());
             if(node.left != null){
        
                 queue.add(node.left);
             }
             if(node.right != null){
        
                 queue.add(node.right);
             }
         }
         return head;
     }
    
    
     //构建节点
     public static Node generateNode(String val){
        
         if(val == null){
        
             return null;
         }
         return new Node(Integer.valueOf(val));
     }

## 二、树的常见面试题 ##

### ①LeetCode - 431.将N叉树编码为二叉树 ###

> 思路：将所有子节点全部放在左边，兄弟节点全部放在右边

1.节点类

//N叉树节点
    public static class Node {
        
        public int val;
        public List<Node> children;
    
        public Node() {
        
        }
    
        public Node(int val, List<Node> children) {
        
            this.val = val;
            this.children = children;
        }
    }
    
    //二叉树节点
    public static class TreeNode {
        
        public int val;
        TreeNode left;
        TreeNode right;
    
        TreeNode(int val) {
        
            this.val = val;
        }
    }

2.编码：【将N叉树变为二叉树】

//将N叉树变为二叉树【编码】
    //【左边放root的孩子，右边放root的兄弟节点】
    public TreeNode encode(Node root){
        
        if(root == null){
        
            return null;
        }
        TreeNode head = new TreeNode(root.val);
        //将root的所有子孩子全部挂载到left
        head.left = en(root.children);
        return head;
    }
    
    //处理root的孩子
    private TreeNode en(List<Node> children){
        
        TreeNode head = null;
        TreeNode cur = null;
        for(Node child : children){
        
            TreeNode tNode = new TreeNode(child.val);
            if(head == null){
        
                head = tNode;
            } else {
        
                //兄弟节点
                cur.right = tNode;
            }
            cur = tNode;
            //【分配节点的孩子】
            cur.left = en(child.children);
        }
        return head;
    }

3.解码：【将二叉树转换为多叉树】

//解码：将二叉树变为多叉树
    public Node decode(TreeNode root){
        
       if(root == null){
        
           return null;
       }
       return new Node(root.val, de(root.left));
    }
    
    public List<Node> de(TreeNode root){
        
       List<Node> children = new ArrayList<>();
       while(root != null){
        
           //左边存放是孩子
           Node cur = new Node(root.val, de(root.left));
           children.add(cur);
           //去找兄弟节点
           root = root.right;
       }
       return children;
    }

### ②二叉树的最大宽度 ###

> 给定一个root节点，返回该二叉树的最大宽度是多少

方法一：使用map

public static int maxWidthUseMap(Node head) {
        
        if (head == null) {
        
            return 0;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        HashMap<Node, Integer> levelMap = new HashMap<>();
        //value : 第几层
        levelMap.put(head, 1);
        //当前所在层数
        int curLevel = 1;
        //当前层是curLevel，宽度目前是多少
        int curLevelNodes = 0;
        int max = 0;
        while (!queue.isEmpty()) {
        
            Node cur = queue.poll();
            int curNodeLevel = levelMap.get(cur);
            if (cur.left != null) {
        
                levelMap.put(cur.left, curNodeLevel + 1);
                queue.add(cur.left);
            }
            if (cur.right != null) {
        
                levelMap.put(cur.right, curNodeLevel + 1);
                queue.add(cur.right);
            }
            //查看是否是当前层，如果是，curLevelNodes++
            if(curNodeLevel == curLevel){
        
                curLevelNodes++;
            } else {
        
                max = Math.max(max, curLevelNodes);
                curLevel++;
                curLevelNodes = 1;
            }
        }
        max = Math.max(max, curLevelNodes);
        return max;
    }

方法二：

/**
     * 不使用map方法【找到当前层及下一层的最右节点】
     * 核心：每层的最右节点
     *
     * @param head
     * @return
     */
    public static int maxWidthNoMap(Node head) {
        
        if (head == null) {
        
            return 0;
        }
        //队列：存放节点
        Queue<Node> queue = new LinkedList<>();
        //头节点不为null，将其放入queue
        queue.add(head);
        Node curNode = head;//当前层节点最右节点
        Node nextEnd = null;
        int curLevelNodes = 0;//每层节点数
        int res = 0;
        while (!queue.isEmpty()) {
        
            //队列弹出当前节点
            Node cur = queue.poll();
            if (cur.left != null) {
        
                queue.add(cur.left);
                //更新下一层最右节点
                nextEnd = cur.left;
            }
            if (cur.right != null) {
        
                queue.add(cur.right);
                nextEnd = cur.right;
            }
            curLevelNodes++;
            res = Math.max(res, curLevelNodes);
            if (cur == curNode) {
        
                //当前节点为当前层的最右节点
                curLevelNodes = 0;
                //当前层的最右节点更新
                curNode = nextEnd;
            }
        }
        return res;
    }