力扣331-验证二叉树的前序序列化

vlambda
2021-03-13

力扣331-验证二叉树的前序序列化

一、原题题目

1.1 题目

序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。

       _9_
      /   \
     3     2
    / \   / \
   4   1  #  6
  / \ / \   / \
 #  # # #  #  #

例如，上面的二叉树可以被序列化为字符串 “9，3，4，#，#，1，#，#，2，#，6，#，#” 其中 # 代表一个空节点。给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 # 。你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 "1,,3" 。

1.2 示例

示例1：

输入： "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出： true
示例2：

输入： "1,#"
输出： false
示例3：

输入： false
输出： false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree

二、解题思路

2.1 利用【递归思想】解题

解题思路

要判断这个字符串是否是一个二叉树的前序序列，如果是，那么根节点的左右子树的序列也必定是一个符合要求的二叉树前序序列。如示例一，当 "9,3,4,#,#,1,#,#,2,#,6,#,#" ，左孩子是节点 3 ，右孩子是节点 2 ，则左子树序列 3，4，#，#，1，#，# 和右子树序列 2，#，6，#，# 都将是一个符合要求的二叉树前序序列。再往下分析就可以得到最简单的二叉树前序序列必定是 # ，或者 n，#，# 。所以当碰到 n，#，# 时，说明节点为 n 的元素作为根节点则下面的都是符合要求的。所以只要是碰到了n，#，# 就将其改成 # 表示它后面的都是符合二叉树的前序序列要求的。

模拟示例一过程："9,3,4,#,#,1,#,#,2,#,6,#,#"

9,3,4,#,# => 9,3,#，继续
9,3,#,1,#,# => 9,3,#,# => 9,#，继续
9,#2,#,6,#,# => 9,#,2,#,# => 9,#,# => #，结束

可以遍历字符串里的每个元素，用 split() 函数将其以 , 分割为多个字符串数组，用一个容器去装每个元素，如果碰到 n,#,# 则将其该为 # ，遍历到结束，如果容器中最后只剩下一个 # 则表示该字符串时一个二叉树的前序序列，返回 true，否则返回 false 。

详细代码（Java）

public static boolean isValidSerialization(String preorder) {
  ArrayList<String> list = new ArrayList<>();     // list 作为容器
  for (String s : preorder.split(",")){        // 用 ，分割字符串并遍历
    list.add(s);                                  // 每个元素加入 list 容器
    int size = list.size();                       // 获取容器中元素个数
    // 判断是否大于三个并且是以 n,#,# 结尾，是则只留下一个 # 
    while (size>=3&&list.get(size-1).equals("#")&&list.get(size-2).equals("#")&&!list.get(size-3).equals("#")){
      list.remove(size-1);
      list.remove(size-3);
      size = list.size();
    }
  }
  return list.size()==1&&list.get(0).equals("#");
}

代码执行结果

效率不是很好，我用了其他容器好像也提升不了多少。

2.2 利用【出入度关系】解题

解题思路

二叉树的也属于图，节点（包括空节点 #）都是由边链接的，从上到下的关系就会有出度和入度的概念。

根节点：2个出度，0个入度

普通节点：2个出度，1个入度

空节点：0个出度，1个入度

最终出度和入度的和相同，都等于边的数目，并且在结束前出度一定大于入度（最终都会以两个空节点结束）

详细代码（Java）

public static boolean isValidSerialization(String preorder) {
    if (preorder.equals("#"))   return true;
    if (preorder.charAt(0)=='#'&&preorder.length()!=1)  return false;
    int d =2;      // 出度减入度之差，根节点提前加上
    boolean b = true;  // 判断是否是根节点 根节点 d+2
    for (String s : preorder.split(",")){
      if (d<=0)    return false;  // 没遍历完的情况下如果入度大于或等于了出度，则一定不是
      if (b){      // 是根节点
        b=false;
        continue;
      }
      if (s.equals("#"))  d--;  // 是空节点 度-2
      else d++;          // 是普通节点 度+1
    }
    return d ==0;     // 遍历完如果度为0 则是
}

代码执行结果

vlambda博客
学习文章列表