Leetcode每日一题-331.验证二叉树的前序序列化

331. 验证二叉树的前序序列化

题目地址

描述

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

Leetcode每日一题-331.验证二叉树的前序序列化

例如,上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#",其中 # 代表一个空节点。

给定一串以逗号分隔的序列,验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。

每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。

你可以认为输入格式总是有效的,例如它永远不会包含两个连续的逗号,比如 "1,,3" 。

示例

示例 1:

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

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

输入: "9,#,#,1"
输出: false

分析

  1. 二叉树的题目其实蕴含很多的规律公式,如果熟悉二叉树的话很容易得到想到这个题的一些思路。

    • 二叉树有这样的规律:

      若度为2的节点有n个,则叶子节点(度为0的节点)有n+1个。

      这个规律其实是通过数学归纳法得来的,如下图:

    Leetcode每日一题-331.验证二叉树的前序序列化

    其实由上面的图例不难发现这样一个规律,每当增加一个叶子节点,有两种情况:

    • 叶子节点A本身是在叶子节点B上增加的,那么相当于B的叶子节点状态转移到A上了,叶子节点数没有变化。
    • 叶子节点A本身实在度为1的节点上增加的,那么增加之后,叶子节点数+1,度为2的节点数+1。
  2. 如果能理解上述的一个规律变化,那么再来看今天的这个题目,其实不就是把叶子节点转化成了#吗?

  3. 而且今天的题目特殊,没有度为1的节点,所有的节点都必须是满的,在先序扫描的时候,就存在这样的关系:

    • "#"的数量比数的数量多1;
    • 先序序列,根左右往后遍历,最后的一个值一定是#;
    • 任何时候,#的数量不能多于数字的数量。

实现

依照上述分析,我们应该能想到如下的实现:(一些题解使用栈,完全没必要,费时费力)

  1. 使用一个标记值flag存储当前的一个序列数;
  2. 当遇到一个数字,那么flag+1
  3. 当遇到一个#号,那么应该有如下的判断:
    • 如果flag=0,说明之前没有数字了
      • 判断当前的#是不是序列的最后一个,是,那么返回序列正确
      • 不是,那么返回序列错误
    • 如果flag!=0,那么flag-1
      • flag为什么-1
      • 参照之前分析里面的图例,每增加一个#,相当于和之前的序列进行了一次抵消
  4. 如果遇到一个,号,那么不做处理,判断下一个字符
  5. 如果字符序列遍历完了还没得到结果,说明字符序列是错的

代码

func isValidSerialization(preorder string) bool {
	n := len(preorder)
	if n == 0 {
        // 如果序列长度为0,返回一个false
        // 注,如果表示空节点,那么应该至少有一个#,所以序列长度为0是false
		return false
	}
    // 记录数字数,和#抵消
	flag := 0
	for i := 0; i < n; {
        // 如果是逗号,不做处理
		if preorder[i] == ',' {
			i++
		}
		if preorder[i] == '#' {
            // flag=0,说明数字全部被抵消了,那么就应该判断当前的#是否是最后一个
			if flag == 0 {
                // i=n-1表示最后一个,!=表示非最后一个
				return i == n-1
			} else {
                // 数字没有被抵消完,那么当前的#去抵消一个数字
				flag--
			}
			i++
		} else {
            // 当前字符不是逗号,不是#号,就只能是数字了
            // 注意一个坑,数字可能不止一个字符,比如10,所以要进行循环判断(我踩了一次坑)
			for i < n && preorder[i] != '#' && preorder[i] != ',' {
                i++
			}
            // 将当前数字记录+1
			flag++
		}
	}
    // 循环未得到结果,说明序列不全,不能成为先序序列
	return false
}

提交结果
Leetcode每日一题-331.验证二叉树的前序序列化

上一篇:105. 从前序与中序遍历序列构造二叉树 + 树遍历


下一篇:【2021-03】剑指offer 中等题 Java复刷