题目链接

英文链接：https://leetcode.com/problems/find-duplicate-subtrees/

中文链接：https://leetcode-cn.com/problems/find-duplicate-subtrees/

题目详述

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

 _9_
/   \

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

#

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

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

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

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

示例 1:

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

示例 2:

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

示例 3:

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

题目详解

一般来说，只给出前序遍历，并不能唯一确定一棵二叉树。但这道题目中还给出了所有空节点的位置，所以可以唯一确定一棵二叉树。
我们用先序顺序递归遍历整棵树，遍历时用一个指针在给定数组中指向当前节点的值，如果遇到 #，则说明遇到了空节点，直接 return；如果遇到整数，说明遍历到了树中的一个节点，我们先将指针后移，表示先输出根节点，然后依次递归遍历左子树和右子树。
如果递归还没结束但数组已经遍历完，或者递归结束但数组还没遍历完，则说明给定的序列不是一个合法的前序遍历。
时间复杂度：递归遍历时只将数组扫描了一遍，所以时间复杂度是 O(n)。

public class LeetCode_00331 {

    public boolean isValidSerialization(String preorder) {
        String[] strs = preorder.split(",");
        int[] index = new int[1];
        boolean[] flag = new boolean[]{true};
        dfs(strs, index, flag);
        return flag[0] && index[0] == strs.length;
    }

    private void dfs(String[] strs, int[] index, boolean[] flag) {
        if (!flag[0]) {
            return;
        }
        if (index[0] == strs.length) {
            flag[0] = false;
            return;
        }
        if (strs[index[0]++].equals("#")) {
            return;
        }
        dfs(strs, index, flag);
        dfs(strs, index, flag);
    }
}

从入度和出度的角度进行考虑，本题会变得更简单。
一个非空结点会提供 1 个入度和 2 个出度（除了根结点，它不提供入度）。
一个空结点会提供 1 个入度和 0 个出度。
记 diff = 出度 - 入度，每来一个结点，diff 要减 1，因为它提供了一个入度。如果这个结点非空，diff 要加 2，因为这个结点提供了 2 个出度。
diff 初始值为 1，遍历完成后 diff 应该为 0。如果不为 0，说明不是合法的前序序列（结点提供的出度没有消耗完）。遍历过程中 diff 不应小于 0。如果小于 0，说明不是合法的前序序列（之前的结点不提供出度，后面的结点也就没有入度）。

public class LeetCode_00331 {

    public boolean isValidSerialization(String preorder) {
        String[] strs = preorder.split(",");
        int diff = 1;
        for (String s : strs) {
            if (--diff < 0) {
                return false;
            }
            if (!s.equals("#")) {
                diff += 2;
            }
        }
        return diff == 0;
    }
}