算法喜刷刷之验证二叉树的前序序列化

关注

发布于: 2021 年 03 月 12 日

题目难度：**中等**

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

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

复制代码

示例 1:

输入: "9,3,4,#,#,1,#,#,2,#,6,#,#"

输出: true

示例 2:

输入: "1,#"

输出: false

示例 3:

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

输出: false

解题步骤：

public boolean isValidSerialization(String preorder) {        int n = preorder.length();        if (n == 0) {            return true;        }
        int n1 = 0;        int n2 = 0;
        String[] arr = preorder.split(",");        for (int i = 0; i < arr.length; i++) {            if (arr[i].equals("#")) {                n1++;            } else {                n2++;            }            if (i != arr.length - 1 && n1 > n2) {                return false;            }        }        return n1 == n2 + 1;
    }

复制代码

思路说明：

我们知道二叉树有一个性质就是整棵树叶子节点的个数比内部节点的个数大 1，当然在遍历的过程中，叶子节点的个数一定是小于等于内部节点的个数的，如果不满足这个条件，证明有根节点为空，直接返回 false，遍历完成后，只需要验证一下上面说的性质就可以了。

发布于: 2021 年 03 月 12 日阅读数: 7

Kylin

关注

现实的理想主义者 2019.10.08 加入

【坐标】：魔都【品种】：程序媛【标签】：技术宅、大吃货【追求】：改变世界、改变自己【信条】：每次前进一小步

发布

暂无评论

创作场景

算法喜刷刷之验证二叉树的前序序列化

Kylin

评论