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

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

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

二叉树节点结构：

//二叉树节点结构
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