刷题_另一个树的子树

发表于2024-04-01更新于2025-11-04阅读次数

内容

原题名叫做：另一个树的子树。总的来说就是找一个树T1中有没有和T2完全结构一样的子树。

分析

要判断树中是否包含某个具体的结构，可以使用遍历序列来判断。
但是要注意：示例2就是一种容易忽略的情况。如果仅仅依靠非空节点的遍历序列去判断，则就会忽略掉T1中的比T2多余的部分，比如：T1的前序遍历为341205，T2的前序遍历为412。虽然T1包含T2的序列412，但是T1的2节点下面还挂着左孩子0。这就导致实际上T1中这个子树和T2结构不完全一样！
所以，还要给叶子节点的空孩子加标记符，比如#代表空。
如此，T1的前序遍历为341##20#5##，T2的前序遍历为41##2##，这样就能区分了。
除此之外：还要在每次写val值（包括空）之后附加个!标记，因为122334有可能是12,23,34，也有可能是1,223,34。这就造成了歧义。
补充一句，前序、中序、后序选择哪一个都可以，只要给出有效节点值、空节点以及访问节点结束标志，就能完全确定一个树的结构。

代码

解1_两树序列化为字符串，判断是否包含子串

Java中字符串不断的拼接一定要用StringBuilder。可以提高效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
package 字符串;
import common.TreeNode;
public class _572_另一个树的子树 {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
         
    }
    // 此处用后序遍历序列来表达树的结构。换成前序、中序也可以。
    private String postSerialize(TreeNode root)
    {
        StringBuilder sb = postSerialize(root, sb);
        return sb.toString();
    }
    private void postSerialize(TreeNode root, StringBuilder sb)
    {
        if(root != null)
        {
            postSerialize(root.left, sb);
            postSerialize(root.right, sb);
            sb.append(root.val);
        }
        else
        {
            sb.append("#");
        }
        sb.append("!");
        return;
    }
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import common.TreeNode;
import common.printer.BinaryTreeInfo;
import common.printer.BinaryTrees;

    public static void main(String[] args)
    {
        TreeNode root = new TreeNode(3);
        root.right = new TreeNode(5);
        root.left = new TreeNode(4);
        TreeNode curRoot = root.left;
        curRoot.left = new TreeNode(1);
        curRoot.right = new TreeNode(2);
        BinaryTrees.println(new BinaryTreeInfo() {
            @Override
            public Object root() {
                return root;
            }
            @Override
            public Object left(Object node) {
                return ((TreeNode)node).left;
            }
            @Override
            public Object right(Object node) {
                return ((TreeNode)node).right;
            }
            public Object string(Object node) {
                return ((TreeNode)node).val;
            }
        });
        System.out.println(postSerialize(root));
    }

结果：

1
2
3
4
5
6
  ┌─3─┐
  │   │
┌─4─┐ 5
│   │
1   2
#!#!1!#!#!2!4!#!#!5!3!

isSubtree函数：对比两个字符串，判断T1字符串是否包含T2字符串。可以调用java的库函数contains。但据说contains用的不是KMP，因此效率可能较低，最好调用KMP算法。

1
2
3
4
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if(root == null || subRoot == null) return false;
    return postSerialize(root).contains(postSerialize(subRoot));
}

坑

虽然前序、中序、后序都可以，但是以上先序遍历转化的字符串有缺陷，仍不能通过T1先序字符串包含T2先序字符串就断定T2一定是T1的子树。比如：T1是33单节点，那么T1的字符串为33!#!#!，T2为3单节点，那么T2的字符串为3!#!#!，可以看到，虽然T1字符串包含T2字符串，但是T2的3节点压根就跟T1的33节点没关系！
于是，可以看到，前序遍历是存在缺陷的，这个缺陷只出现在顶点打印的歧义。
中序、后序都没有这样的问题。所以，如果是用前序遍历来序列化树，那么要在打印的最开始再另加一个标志如?，如此：T1字符串变为?33!#!#!，T2字符串变为?3!#!#!，由此就可以判别出，T1字符串不包含T2字符串了，因此可以正确判断出，T2不是T1的子树。

心得

这个题目属于二叉树的结构方面的问题，类似这类题型，考虑利用二叉树序列的特点和意义，转化为字符串序列，相当于把不好解决的树形结构降维打击成了一维结构。所以，本质上，这个题目考察的是二叉树的序列化、反序列化。

总结

  1. 非空节点：值!，空节点：#!
  2. 空节点也必须序列化，才能完整地表达唯一的一棵树，而且前序、中序、后序遍历都可以确定一棵树，但是层序遍历不可以。

刷题_有效的字母异位词

发表于2024-04-01更新于2025-11-04阅读次数

内容

原题名叫做：有效的字母异位词。给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。（只包含小写字母）

举例：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入: s = "anagram", t = "nagaram"
输出: true

输入: s = "rat", t = "car"
输出: false

提示:

1. 1 <= s.length, t.length <= 5 * 104
2. s 和 t 仅包含小写字母
 

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

即每种字母的数目一样，但是顺序不一定。

分析

若是有限个字母比如26个英文字母，则可以建立一个一维数组S，遍历s，计每种祖母数。然后再建立一个一维数组T，遍历t，计数。最后判断S和T的内容是否一样。

代码

解1_

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    bool isAnagram(string s, string t) {
        std::vector<int> vis = std::vector<int>(26);
        std::vector<int> vit = std::vector<int>(26);
        const char * cp = s.c_str();
        while(*cp != '\0')
        {
            ++vis[*cp++ - 'a'];
        }
        cp = t.c_str();
        while(*cp != '\0')
        {
            ++vit[*cp++ - 'a'];
        }
        int i = 0;
        while(i < 26)
        {
            if(vis[i] != vit[i++])
            {
                return false;
            }
        }
        return true;
    }
};

优化

可以不用去创建另外一个数组，而是在遍历t的过程中去减第一个数组中的value，遇到小于零的情况则false。（这已经足够了，不需要去判断第一个数组中是否全部为0了。因为前置条件已经限制两串长度一致，假如2号串中出现1串中不一样的字符，肯定会出现负值。如果2号串的字符种类没有多出来的，而数目多，比如1号串car，2号串raa，则a的值也会出现负值）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.length() != t.length()) return false;
        if(s.length() == 0) return false;
        std::vector<int> vis = std::vector<int>(26);
        const char * cp = s.c_str();
        while(*cp != '\0')
        {
            ++vis[*cp++ - 'a'];
        }
        cp = t.c_str();
        while(*cp != '\0')
        {
            if(--vis[*cp++ - 'a'] < 0)
            {
                return false;
            }
        }
        return true;
    }
};

坑

解2_hashmap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<unordered_map>
class Solution {
public:
    bool isAnagram(string s, string t) {
        //using std::hash_map<char, int> = CharIntMap;
        if(s.length() != t.length()) return false;
        if(s.length() == 0) return false;
        typedef std::unordered_map<char, int> CharIntMap;
        CharIntMap charIntMap_s;
        const char * cp = s.c_str();
        while(*cp != '\0')
        {
            ++charIntMap_s[*cp++];
        }
        CharIntMap charIntMap_t;
        cp = t.c_str();
        while(*cp != '\0')
        {
            ++charIntMap_t[*cp++];
        }
        for(auto it = charIntMap_s.begin(); it != charIntMap_s.end(); ++it)
        {
            if(charIntMap_t[it->first] != it->second)
            {
                return false;
            }
        }
        return true;
    }
};

心得

这个题目属于

总结