当前位置:   article > 正文

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

树序列

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

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

二叉树节点结构:

//二叉树节点结构
public static class Node {
    public int value;
    public Node left;
    public Node right;

    public Node(int data) {
        this.value = data;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

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
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

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));
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

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;
 }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

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));
 }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

二、树的常见面试题

①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;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

②二叉树的最大宽度

给定一个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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

方法二:

/**
 * 不使用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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/不正经/article/detail/681766
推荐阅读
相关标签
  

闽ICP备14008679号