算法题——树的子结构

￡神魔★判官ぃ 2024-03-23 23:29 51阅读 0赞

###### 声明 ######

该系列文章仅仅展示个人的解题思路和分析过程，并非一定是优质题解，重要的是通过分析和解决问题能让我们逐渐熟练和成长，从新手到大佬离不开一个磨练的过程，加油！

###### 原题链接 ######

[树的子结构![icon-default.png_t_N6B9][]https://leetcode.cn/leetbook/read/illustration-of-algorithm/5dshwe/][icon-default.png_t_N6B9_https_leetcode.cn_leetbook_read_illustration-of-algorithm_5dshwe]

###### 算法分析 ######

根据题目可以获得以下三个信息：

1.树的子结构：如图1中的(2)是不属于(1)，而属于(3)的子结构，(4)是属于(1)，而不属于(3)的子结构。

2.空树不是任意一个树的子结构。

3.题目中的树均为二叉树。

![e00d707d734749819ee8e619562b3b8f.jpeg][] 图1

然后明确两个问题：

（1）空树怎么判断？

空树即为节点为空的树。

（2）如何判断树B是否为树A的子结构？

在树A中找到与树B的root节点值相同的节点，保存在一个列表中，然后依次以列表中的节点作为起始节点在树A中进行遍历，遍历过程中记录树B中剩余待遍历节点的数量count。

①若count为0，则表示树B遍历完毕则return True；

②若当前树B的节点为空则return True；

③若当前树A与树B的节点值相同则遍历二者的左右节点，重复①②③④；

④其它情况return False；

###### 代码示例（C\#） ######

//二叉树节点
    public class TreeNode
    {
        public int val;
        public TreeNode? left;
        public TreeNode? right;
    
        public TreeNode(int x)
        { val = x; }
    }
    
    public bool IsSubStructure(TreeNode A, TreeNode B)
    {
        //检测是否为空树
        if (A == null || B == null) return false;
        //查询树A中与树B的root节点值相同的节点，并将它们保存在列表中
        List<TreeNode> rootNodes = new List<TreeNode>();
        FindRootNode(A, B, ref rootNodes);
        //如果树A中不存在与树B的root节点值相同的节点则返回false
        if (rootNodes.Count == 0) return false;
        int count = 1;//记录子树中剩余待查询的节点数
        foreach (TreeNode node in rootNodes)
        {
            //每个节点都将作为一次搜索的起始点
            if (Search(node, B, ref count)) return true;
            count = 1;
        }
        return false;
    }
    
    //搜索方法
    //参数:树A的节点，树B的节点，树B中剩余待查询的节点数
    private bool Search(TreeNode? A, TreeNode? B, ref int count)
    {
        if (count == 0) return true;//树B搜索完毕
        else if (B == null) return true;//树B的节点为空
        else if (A != null && B != null)
        {
            if (A.val == B.val)
            {
                count--;
                if (B.left != null) count++;
                if (B.right != null) count++;
                return Search(A.left, B.left, ref count) && Search(A.right, B.right, ref count);
            }
        }
        return false;
    }
    
    //寻找树A中与树B的root节点相同的节点的方法
    //参数:树A的节点，树B的节点，root节点列表
    private void FindRootNode(TreeNode? A, TreeNode B, ref List<TreeNode> rootNodes)
    {
        if (A == null) return;
        if (A.val == B.val) rootNodes.Add(A);
        if (A.left != null) FindRootNode(A.left, B, ref rootNodes);
        if (A.right != null) FindRootNode(A.right, B, ref rootNodes);
    }

###### 算法解说 ######

结合题目描述，我们可以明确什么是一棵树的子结构以及空树不作为任何树的子结构，在这个基础上我们去挖掘题目的变量和逻辑主体，因为二者是我们将分析思路转换为代码的关键点。粗略一看本题似乎并不需要单独定义什么变量，而逻辑主体则包括怎么判断空树以及如何确定一棵树是否为另一棵树的子结构，这两个问题我们在算法分析中进行了解答。

但是在逻辑主体中我们很容易忽略一个特殊情况，例如我们需要判断树B是否为树A的子结构，那么我们需要先在树A中找到与树B的root节点相同的节点，但是相同的节点可能不止一个，这是我们需要去考虑的问题，题目并没有规定一棵树中不能存在相同节点。因此，在我们判断树B是否为树A的子结构之前应该在树A中找到所有与树B的root节点相同的节点，并且让它们依次作为root节点去进行判断。这也就是FindRootNode方法的由来，因此我们还是需要一个变量用来存储这些root节点。

所以事实上我们还是需要两个变量，一个用来记录子树中剩余待查询的节点数，另一个用来存储root节点集合。

现在明确了本题的变量和逻辑主体，那么将思路转换为代码就比较快捷了。

[icon-default.png_t_N6B9]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/1e1038c5f72f4a3bba98d426cc6f1f26.png
[icon-default.png_t_N6B9_https_leetcode.cn_leetbook_read_illustration-of-algorithm_5dshwe]: https://leetcode.cn/leetbook/read/illustration-of-algorithm/5dshwe/
[e00d707d734749819ee8e619562b3b8f.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/7f625340243f4796be93d57650451493.png