二叉树专题突破-构造法与序列化

Java leetcode
数据结构与算法
发布日期:   2023-01-20

1. 构造最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

  1. 创建一个根节点，其值为 nums 中的最大值。
  2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
  3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的最大二叉树 。

首先这道题,通过问题分析可见:要构造出一个节点,必须满足如下条件

  • 构造出本节点
  • 构造出本节点的左子树
  • 构造出本节点的右子树

可以看到问题需要我们先计算出节点的左右子树的结果,因此在这样的情况下,采用后序遍历+分解子问题的方式比较合适,写出的代码如下:

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return constructMaxTree(nums,0,nums.length-1);
    }

    private TreeNode constructMaxTree(int[] nums,int begin,int end){
        if(begin > end){
            return null;
        }
        //寻找最大值
        int maxIndex = begin;
        for(int i = begin;i<=end;i++){
            if(nums[i] > nums[maxIndex]){
                maxIndex = i;
            }
        }
        TreeNode leftNode = constructMaxTree(nums,begin,maxIndex-1);
        TreeNode rightNode = constructMaxTree(nums,maxIndex+1,end);
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = leftNode;
        root.right = rightNode;
        return root;
    }

}

上面这道题总结一下:首先第一点是每一个节点要完成的工作,

2. 从前序与中序遍历序列构造二叉树

  1. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

class Solution {
    private Map<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i = 0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        return construct(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }

    private TreeNode construct(int[] preorder,int preStart,int preEnd,
                               int[] inorder,int inStart,int inEnd)
    {
        if(preStart > preEnd){
            return null;
        }
        //先找到根元素
        int rootVal = preorder[preStart];
        //然后在中序遍历数组中找到这个根元素
        int inIndex = map.get(rootVal);
        TreeNode root = new TreeNode(rootVal);
        int leftSize = inIndex - inStart;
        root.left = construct(preorder,preStart+1,preStart+leftSize,inorder,inStart,inIndex-1);
        root.right = construct(preorder,preStart+leftSize+1,preEnd,inorder,inIndex+1,inEnd);
        return root;
    }
    
}

3. 二叉树的序列化与反序列化

  1. 二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

public class Codec {
    // Encodes a tree to a single string.
    private final static String SEP = ",";
    private final static String NULL = "#";
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        traverse(root,sb);
        return sb.toString();
    }
    private void traverse(TreeNode root,StringBuilder sb){
        if(root == null){
            sb.append(NULL).append(SEP);
            return ;
        }
        /*前序遍历的方案*/
        sb.append(root.val).append(SEP);
        traverse(root.left,sb);
        traverse(root.right,sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] nodes = data.split(SEP);
        LinkedList<String> list = new LinkedList<>();
        for (String node : nodes) {
            list.addLast(node);
        }
        return deserialize(list);
    }

    private TreeNode deserialize(LinkedList<String> nodes){
        if(nodes == null){
            return null;
        }
        //按照前序遍历的方式构造
        String rootVal = nodes.removeFirst();
        if(rootVal.equals(NULL)){
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(rootVal));
        root.left = deserialize(nodes);
        root.right = deserialize(nodes);
        return root;
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    private static final String SEP = ",";
    private static final String NULL = "#";
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        traverse(root,sb);
        return sb.toString();
    }
    private void traverse(TreeNode root,StringBuilder sb){
        //后序遍历方式
        if(root == null){
            sb.append(NULL).append(SEP);
            return ;
        }
        traverse(root.left,sb);
        traverse(root.right,sb);
        sb.append(root.val).append(SEP);
        return;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] nodes = data.split(SEP);
        LinkedList<String> list = new LinkedList<>();
        for(String node:nodes){
            list.addLast(node);
        }
        return deserialize(list);
    }

    private TreeNode deserialize(LinkedList<String> list){
        if(list == null){
            return null;
        }
        //后序遍历方式回来构造
        String rootVal = list.removeLast();
        if(rootVal.equals(NULL)){
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(rootVal));
        root.right = deserialize(list);
        root.left = deserialize(list);
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    private static final String SEP = ",";
    private static final String NULL = "#";
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null){return null;}
        Queue<TreeNode> q = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        q.offer(root);
        while(!q.isEmpty()){
            TreeNode head = q.poll();
            if(head == null){
                sb.append(NULL).append(SEP);
                continue;
            }
            sb.append(head.val).append(SEP);
            q.offer(head.left);
            q.offer(head.right);
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null){
            return null;
        }
        String[] nodes = data.split(SEP);
        Queue<TreeNode> q = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        q.offer(root);
        int i = 1;
        while(i<nodes.length){
            TreeNode head =  q.poll();
            String leftVal = nodes[i++];
            if(leftVal.equals(NULL)){
                head.left = null;
            }else{
                head.left = new TreeNode(Integer.parseInt(leftVal));
                q.offer(head.left);
            }
            String rightVal = nodes[i++];
            if(rightVal.equals(NULL)){
                head.right = null;
            }else{
                head.right = new TreeNode(Integer.parseInt(rightVal));
                q.offer(head.right);
            }
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

4. 寻找重复的子树

给你一棵二叉树的根节点 root ，返回所有 重复的子树 。

对于同一类的重复子树，你只需要返回其中任意 一棵 的根结点即可。

如果两棵树具有 相同的结构 和 相同的结点值 ，则认为二者是 重复 的。

对于这道题而言,我们首先需要思考,如何来比较两棵树是否相同?

  • 第一点假设我需要找出所有重复的子树,那么我就需要遍历整棵树的节点,看以这些节点为根的子树长什么样
  • 第二点,如何判断这些子树是否相同呢?那我就必须有一种结构来描述子树的形状,通过3我们已经掌握了如何将树序列化,那么我们同理也可以,将某个节点的遍历序列化后的结果作为结构进行比较

一旦题目提到了子树相关的内容,一般就是要使用后序遍历了

private Map<String,Integer> map = new HashMap<>();
private List<TreeNode> list = new LinkedList<>();

public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
    if(root == null){
        return null;
    }
    getAllNodeStruct(root);
    return list;
}

private String getAllNodeStruct(TreeNode root){
    if(root == null){
        return "#";
    }
    String left = getAllNodeStruct(root.left);
    String right = getAllNodeStruct(root.right);
    String rootStruct = left+","+right+","+root.val;
    Integer count = map.get(rootStruct);
    if(count != null && Integer.valueOf(count) == 1){
        list.add(root);
        map.put(rootStruct,2);
    }else if(count == null){
        map.put(rootStruct,1);
    }
    return rootStruct;
}
文章作者: 穿山甲
文章链接: https://lumxi.github.io/2023/01/20/algorithm/book/bin-tree-2/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 穿山甲 !
Java leetcode
赏
  目录