52、序列化二叉树

原文：https://blog.csdn.net/qq_27703417/article/details/70958692

题目：首先我们介绍二叉树先序序列化的方式，假设序列化的结果字符串为str，初始时str等于空字符串。先序遍历二叉树，如果遇到空节点，就在str的末尾加上“#!”，“#”表示这个节点为空，节点值不存在，当然你也可以用其他的特殊字符，“!”表示一个值的结束。如果遇到不为空的节点，假设节点值为3，就在str的末尾加上“3!”。现在请你实现树的先序序列化。

给定树的根结点root，请返回二叉树序列化后的字符串。

思路：我们知道所谓的二叉树是一种由对象引用将多个结点关联起来的抽象数据结构，是存在于内存中的，不能进行持久化，如果需要将一颗二叉树的结构持久化保存，需要将其转换为字符串并保存到文件中，于是关键是建立一套规则，使得二叉树可以与字符串一一对应，根据一个二叉树可以唯一的得到一个字符串，根据一个字符串也可以唯一的还原出一棵二叉树。

所谓序列化也叫持久化，显然序列化需要将每个结点按照一定的顺序转换为字符串，关键是这个顺序是什么顺序，这个顺序其实就是遍历树的顺序，按照遍历结点的顺序将结点转化为字符串即可，因此先序遍历、中序遍历、后序遍历、按层遍历都可以进行序列化。当然也有区别：

遍历时对于为null的结点在判断条件中会直接跳过或者返回，但是在序列化时，对于为null的结点也需要遍历并将其对应为”#!”，即在序列化时对于任何null或者非null的结点都需要遍历和处理。这里要理解几点：首先，是不是不存在的结点都需要遍历为null，例如上图中②没有右结点，要遍历为null，⑦没有左右结点要遍历为null，null，再往下，例如⑦的子节点的子节点也不存在，但是不需要遍历为null，因此我们只是对非空的结点进行遍历，在遍历每个非空的结点时关注它的子节点是否为null，如果为null就为字符串加上“#！”并且不再继续遍历，如果不为null就继续遍历。

其实还有另一种解决思路，即还是按照原来的先序、中序、后序、按层遍历的方式进行遍历，我们知道遍历时会遍历到每个非null的结点，但是程序如何知道一个结点是否为null呢，显然在程序遍历到这个结点之前是不知道这个结点是否为null的，只有遍历到了这个结点，才能判断其是否为null，如果为null那么说明这条路径已经遍历完成了，从而可以采取return或者其他的操作，也就是说，只要是遍历方法，它对每一个结点（不管是null还是非null）都要遍历到，即对于②的右结点，④的左右结点，⑦⑧的左右结点，虽然是null但是都是遍历过的，如果没有遍历到这个结点那么就无法保证后面没有结点，也就无法保证对所有结点进行遍历，因此对于任何一个遍历方法，都会遍历到为null的结点，然后对于这些为null的结点就不再往下遍历了。通常对于这些null结点的遍历隐藏在循环或者递归的边界条件处，例如循环时while(cur!=null)那么就要在while循环的外面就是cur==null，于是在循环外边添加逻辑，例如输出“#！”即可。在循环内部，只要在任何if(cur!=null)的地方添加一个else{}逻辑，用来对cur==null时的情况进行处理，即也就是只有这2个位置需要更改：一个是循环内部if(cur!=null)处添加else{cur==null}；另一个是循环体结束时while(cur!=null)时在外面添加一个cur==null的处理逻辑。

于是可以对递归或者非递归的遍历方法进行简单的改造即可，对于递归方法还是很简单，只需要在递归方法的边界条件if(cur==null) return；的return前面添加一个输出“#！”的简单逻辑即可。

 

  

   

    
   
   

    

     import java.util.*;
    
   
  

   

    
   
   

    

     //使用递归先序遍历对二叉树进行序列化
    
   
  

   

    
   
   

    

     public 
     class TreeToString {
    
   
  

   

    
   
   

    
 
     public String toString(TreeNode root) {
    
   
  

   

    
   
   

    
 
     //注意：Java中String是不可改变的，不能进行引用传递，改为使用StringBuffer
    
   
  

   

    
   
   

    

      StringBuilder res=
     new StringBuilder(
     "");
    
   
  

   

    
   
   

    
 
     //调用递归方法完成二叉树遍历序列化
    
   
  

   

    
   
   

    
 
     this.preOrder(root,res);
    
   
  

   

    
   
   

    
 
     //返回结果
    
   
  

   

    
   
   

    
 
     return res.toString();
    
   
  

   

    
   
   

    

      }
    
   
  

   

    
   
   

    
 
    
   
  

   

    
   
   

    
 
     //递归方法，用来先序遍历二叉树同时将其序列化为字符串
    
   
  

   

    
   
   

    
 
     private void preOrder(TreeNode root, StringBuilder str){
    
   
  

   

    
   
   

    
 
     //递归结束的边界条件
    
   
  

   

    
   
   

    
 
     if(root==
     null){
    
   
  

   

    
   
   

    

      str.append(
     "#!");
    
   
  

   

    
   
   

    
 
     return;
    
   
  

   

    
   
   

    

      }
    
   
  

   

    
   
   

    
 
    
   
  

   

    
   
   

    
 
     //先遍历根结点
    
   
  

   

    
   
   

    

      str.append(root.val+
     "!");
    
   
  

   

    
   
   

    
 
     //遍历左子树
    
   
  

   

    
   
   

    
 
     this.preOrder(root.left,str);
    
   
  

   

    
   
   

    
 
     //遍历右子树
    
   
  

   

    
   
   

    
 
     this.preOrder(root.right,str);
    
   
  

   

    
   
   

    

      }
    
   
  

   

    
   
   

    

     }
    
   
 
 

千万注意：在Java中String是一种不可改变的对象，无法进行引用传递，因此上面程序中，如果调用方法时传入的是String str,即使用this.preOrder(root,str);那么经过preOrder()方法后str并不会改变，即调用函数中的str和被调用函数中的str不是同一个对象，可以将String理解为一种特殊的对象，不可以进行引用传递。在Java中要使用字符串时最好使用的是StringBuilder或者是StringBuffer，2者基本相同，是关于字符串的对象，和普通对象一样，可以进行引用传递，而且由于实现了缓冲等功能，功能更加强大，因此使用StringBuilder或者StringBuffer来替代，2者的函数基本相同，都有append()等方法，几个主要的差别如下：

常识：StringBuilder与StringBuffer的差别：

1. 在执行速度方面的比较:StringBuilder > StringBuffer>String

2.StringBuffer与StringBuilder，他们是字符串变量，是可改变的对象，每当我们用它们对字符串做操作时，实际上是在一个对象上操作的，不像String一样创建一些对象进行操作，所以速度就快了。

3. StringBuilder:线程非安全的而StringBuffer:线程安全的

当我们在字符串缓冲去被多个线程使用是，JVM不能保证StringBuilder的操作是安全的，虽然他的速度最快，但是可以保证StringBuffer是可以正确操作的。当然大多数情况下就是我们是在单线程下进行的操作，所以大多数情况下是建议用StringBuilder而不用StringBuffer的，就是速度的原因。

对于三者使用的总结:

1.如果要操作少量的数据用 = String

 2.单线程操作字符串缓冲区 下操作大量数据 = StringBuilder

 3.多线程操作字符串缓冲区 下操作大量数据 = StringBuffer

因此在编程练习中通常使用StrignBuilder

 

除了可以使用递归的遍历方式进行序列化，还可以使用非递归的方式进行序列化。

遍历方法还是相同的，只是现在对于弹出的结点cur，在压入cur.left和cur.right时，不管left和right是否是null都要压入到栈中，在弹出结点时进行判断，如果是null结点，那么添加“#！”并且再次弹出一个结点，如果是!=null，那么添加“val!”，即在序列化时，关键是找到null结点何时输出。常识：栈中可以压入null元素。

 

  

   

    
   
   

    

     import java.util.*;
    
   
  

   

    
   
   

    

     //使用非递归先序遍历对二叉树进行序列化
    
   
  

   

    
   
   

    

     public 
     class TreeToString {
    
   
  

   

    
   
   

    
 
     public String toString(TreeNode root) {
    
   
  

   

    
   
   

    
 
     //注意：Java中String是不可改变的，不能进行引用传递，改为使用StringBuffer
    
   
  

   

    
   
   

    

      StringBuilder res=
     new StringBuilder(
     "");
    
   
  

   

    
   
   

    
 
     //调用递归方法完成二叉树遍历序列化
    
   
  

   

    
   
   

    
 
     this.preOrder(root,res);
    
   
  

   

    
   
   

    
 
     //返回结果
    
   
  

   

    
   
   

    
 
     return res.toString();
    
   
  

   

    
   
   

    

      }
    
   
  

   

    
   
   

    
 
    
   
  

   

    
   
   

    
 
     private void preOrder(TreeNode root,StringBuilder str){
    
   
  

   

    
   
   

    
 
     //①创建一个栈,菱形符
    
   
  

   

    
   
   

    

      Stack<TreeNode> stack=
     new Stack<>();
    
   
  

   

    
   
   

    
 
     //②创建指针cur表示当前正在访问的结点,初始值为root
    
   
  

   

    
   
   

    

      TreeNode cur=root;
    
   
  

   

    
   
   

    
 
     //③将根结点放入栈中
    
   
  

   

    
   
   

    

      stack.push(cur);
    
   
  

   

    
   
   

    
 
     //④循环，弹栈--右左结点入栈--弹栈……
    
   
  

   

    
   
   

    
 
     while(!stack.isEmpty()){
    
   
  

   

    
   
   

    
 
     //从栈顶弹出一个结点cur,弹出的可能是null
    
   
  

   

    
   
   

    

      cur=stack.pop();
    
   
  

   

    
   
   

    
 
     if(cur==
     null){
    
   
  

   

    
   
   

    

      str.append(
     "#!");
    
   
  

   

    
   
   

    

      }
     else{
    
   
  

   

    
   
   

    
 
     //只要cur！=null不管cur的left和right是否是null都要压入栈中
    
   
  

   

    
   
   

    

      str.append(cur.val).append(
     "!");
    
   
  

   

    
   
   

    

      stack.push(cur.right);
    
   
  

   

    
   
   

    

      stack.push(cur.left);
    
   
  

   

    
   
   

    

      }
    
   
  

   

    
   
   

    

      }
    
   
  

   

    
   
   

    

      }
    
   
  

   

    
   
   

    

     }
    
   
 
 

二叉树的反序列化

所谓反序列化是根据一个字符串重新建立一棵二叉树，反序列化是序列化的逆过程，对于一个字符串，首先按照分隔符！将其分割为字符串数组，每个字符串元素代表一个结点，然后开始重建二叉树。由于每个结点再字符串中只保留了一个val值，因此需要根据结点的值val重新构建TreeNode结点对象，并且为这个结点对象的left和right进行赋值。

反序列化比序列化要难，其实代码实现是类似的，只也是使用递归，只是这时候是反向的递归，比较抽象，要逐渐理解。已知一个用！分割的字符串是某个二叉树按照先序遍历顺序序列化得到的字符串，将其反序列化建立一棵二叉树，注意，要进行反序列化必须要知道这个字符串是按照什么顺序序列化得到的，只有按照相同的遍历顺序对其进行反序列化才能恢复正确的二叉树。一般使用先序遍历顺序进行序列化和反序列化。在反序列化时，首先得到一个字符串数组strs[]表示字符串序列拆分得到的字符串数组，数组的每个元素字符串对应一个结点的值，可以是3！或者是#！，分别表示一个非空的结点或者是空结点。即要求实现的功能是：根据给定的字符串数组strs[]，重建一棵二叉树并返回这棵二叉树的头结点root。

分析：对于字符串数组strs[]，第1个元素是根结点，第2个元素是左结点，第3个元素可能是第2个结点的左结点或者是第1个结点的右结点，要根据第2个结点是否为null来确定，即对于strs[]，里面的元素必然是按照：根结点à左结点à左结点à左结点（null）à右结点à左结点à左结点（null）à右结点的顺序来排列的，因此总是先递归地恢复建立左结点，当遇到null时，说明这条路径结束了，node结点的left为null，应该返回到node结点并开始恢复一个右结点，此时相当于一个新的重复的过程，可以把这个右结点当做root开始新的递归过程。

即要求实现一个递归方法private TreeNode deSerialize(String[] strs)；对于一个(或者部分)字符串数组，恢复一棵二叉树，并返回这棵二叉树的根结点。

逐个遍历数组strs[],当遇到“#”说明这是一个空结点，在这个根结点的后面不可能建立二叉树，于是相当于建立子树工作完成，返回根结点即返回null即可；如果遇到的是非空的字符串，例如“3”,表明这是一个非空的结点，首先建立这个结点TreeNode newNode=new TreeNode(3)；但是此时仅仅恢复了一个结点，还要恢复它的子树，并且是先恢复左子树，再恢复右子树。如何恢复左子树？显然要根据数组strs[]的下一个元素开始的数组部分来恢复一棵二叉树，这就是这个递归函数的功能（根据一个或者部分字符串数组来建立一棵二叉树），于是调用自身这个递归函数即可，只是此时使用的字符串向后面移动了1个元素而已。

调用完这个函数后，就要认为结点③的左子树已经恢复完毕了，于是开始恢复结点③的右子树newNode.right；恢复右子树的过程还是一样的，也是相同的逻辑（根据一个或者部分字符串数组来建立一棵二叉树），只是此时恢复的二叉树连接到的不是newNode.left上面而是newNode.right上面，当调用完这个函数后，就认为结点newNode的右子树已经恢复完成了，于是整个newNode的val有了，left、right都有了值，于是整棵二叉树就建立了，此时根据函数功能的要求，要返回这棵建立起来的二叉树的根结点，于是返回newNode即可。

常识：没有构造方法时默认有参数为空的构造函数可以不写；当写有含参的构造方法时，如果不写参数为空的构造方法，就不能再使用TreeNode newNode=new TreeNode()这种构造方法，如果要用就必须显示地定义参数为空的构造方法。

 

  

   

    
   
   

    

     public 
     class Solution {
    
   
  

   

    
   
   

    
 
     //已知由先序遍历得到的字符串str,将其恢复为一棵二叉树，并返回根结点
    
   
  

   

    
   
   

    
 
     TreeNode Deserialize(String str) {
    
   
  

   

    
   
   

    
 
     //特殊输入
    
   
  

   

    
   
   

    
 
     if(str==
     null||str.length()<=
     0) 
     return 
     null;
    
   
  

   

    
   
   

    
 
     //将字符串按照","拆分为数组
    
   
  

   

    
   
   

    

      String[] strs=str.split(
     ",");
    
   
  

   

    
   
   

    
 
     //调用递归方法deSerializeCore()方法来实现重建二叉树的功能,返回根结点
    
   
  

   

    
   
   

    

      TreeNode root=
     this.deSerializeCore(strs);
    
   
  

   

    
   
   

    
 
     //注意返回结果
    
   
  

   

    
   
   

    
 
     return root;
    
   
  

   

    
   
   

    

      } 
    
   
  

   

    
   
   

    

     //注意：这里关键是要设计一个成员变量index用于在每次递归调用时能够使用不同的字符串来建立根结点
    
   
  

   

    
   
   

    
 
     int index=
     0;
    
   
  

   

    
   
   

    

     //设计一个递归方法deSerializeCore用于使用strs[]数组的后面部分元素来建立一棵二叉树，并返回根结点
    
   
  

   

    
   
   

    

     //递归方法可以有返回值或者没有返回值，不影响使用，如果有返回值要注意接收
    
   
  

   

    
   
   

    
 
     private TreeNode deSerializeCore(String[] strs){
    
   
  

   

    
   
   

    
 
     if(
     "#".equals(strs[index])){
    
   
  

   

    
   
   

    
 
     //如果遇到的是#表示空节点，不再建立子树，这个结点null就是子树的根结点返回
    
   
  

   

    
   
   

    
 
     //千万注意，返回前要将index向下移动，之后使用的是strs[]中后面部分的元素
    
   
  

   

    
   
   

    

      index++;
    
   
  

   

    
   
   

    
 
     return 
     null;
    
   
  

   

    
   
   

    

      }
     else{
    
   
  

   

    
   
   

    
 
     //如果不为空结点，则先恢复这个结点
    
   
  

   

    
   
   

    

      TreeNode newNode=
     new TreeNode(
     0);
    
   
  

   

    
   
   

    

      newNode.val=Integer.parseInt(strs[index]);
    
   
  

   

    
   
   

    
 
     //千万注意在递归调用之前(使用了一个元素建立结点之后)，要将index向后移动1位
    
   
  

   

    
   
   

    

      index++;
    
   
  

   

    
   
   

    
 
     //恢复左子树
    
   
  

   

    
   
   

    

      newNode.left=
     this.deSerializeCore(strs);
    
   
  

   

    
   
   

    
 
     //恢复右子树
    
   
  

   

    
   
   

    

      newNode.right=
     this.deSerializeCore(strs);
    
   
  

   

    
   
   

    
 
     //建立二叉树完成，返回根结点
    
   
  

   

    
   
   

    
 
     return newNode;
    
   
  

   

    
   
   

    

      }
    
   
  

   

    
   
   

    

      }
    
   
  

   

    
   
   

    

     }
    
   
 
 

理解：上面使用index来指示使用的strs[]中的某个字符串元素来构造结点，每次调用递归方法表示使用一个新的字符串strs[index]，但是递归函数中没有对index作数组访问越界的判断和处理，是否会出现数组越界的问题呢？其实不会，因为在这个递归调用过程中，每次递归调用访问一个元素，同时每次递归调用会返回一个结点，因此最终当结点全部返回时递归函数就结束了，index不会有机会超过strs[]的范围，因此不可能出现index越界的情况，于是可以不用处理，即这里由于已知这棵二叉树是必然可以建立的，因此必然会在数组越界之前完成二叉树的建立和返回。

视频(3)

子树的概念

平衡二叉树（AVL树）

平衡二叉树又叫作AVL树，所谓平衡二叉树是指对于这棵树中的任意根结点，他的左子树和右子树的高度是平衡的，即高度差是0或者1，何为子树的高度？所谓树的高度是指从根结点开始到叶子结点的最长的路径上的结点的数目(与书上有所不同但是以此为准)，因此如果一棵二叉树，上面的任何根结点的左右子树的高度差小于1，那么这棵树就是平衡二叉树。直观的来看，如果某个结点开始的左边的最长路径与右边的最长路径的长度差大于1，那么这个结点就是不平衡的，即以该结点为根的树是不平衡的；反之，如果任何一个结点的左右最长路径都小于等于1，那么这棵树就是平衡的二叉树。