树的子结构 - 遍历子树

「爱情、让人受尽委屈。」 2022-12-20 11:27 154阅读 0赞

## 树的子结构 ##

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)  
B是A的子结构， 即 A中有出现和B相同的结构和节点值。

**例如:**  
给定的树 A:

3
        / \
       4   5
      / \
     1   2

给定的树 B：

4 
      /
     1

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

**示例 1：**  
输入：A = \[1,2,3\], B = \[3,1\]  
输出：false

**示例 2：**  
输入：A = \[3,4,5,1,2\], B = \[4,1\]  
输出：true  
限制：

0 <= 节点个数 <= 10000

--------------------

## 分析 ##

> 遍历A的所有子树，拿来与B树作比较就可以了。

## 解法 ##

bool aha(struct TreeNode* A, struct TreeNode* B){ 
        // 如果A节点为空，B不为空，说明此时已经不匹配，返回false
        if(A == NULL && B){ 
            return false;
        }
        // 如果B为空，说明当前节点是空节点，从某处到此的一个分支已经完成了，如果没有false出现，说明这个子树是A的子树
        if(B == NULL){ 
            return true;
        }
        // A与B不等，且B不为空
        if(A->val != B->val && B != NULL)
            // 此时应该return false，因为当前节点不一定是原始B的根节点，所以不能继续向下判断
            return false;
        // 如果AB相同，此时可以往下遍历，确保AB的左右子树都相同
        if(A->val == B->val){ 
            return aha(A->left, B->left) && aha(A->right, B->right);
        }
        return false;
    }
    
    void dfs_A(struct TreeNode* A, struct TreeNode* B, bool *flag){ 
        // 如果A为空了，不继续往下遍历
        if(A == NULL){ 
            return;
        }
        // A子树与B比较
        if(aha(A, B)){ 
            // A, B匹配成功
            *flag = true;
            return;
        }
        else{ 
            // 遍历A树，
            dfs_A(A->left, B, flag);
            dfs_A(A->right, B, flag);
        }
    }
    
    bool isSubStructure(struct TreeNode* A, struct TreeNode* B){ 
        //代码的鲁棒性，空树，算吗？
        if(A == NULL && B == NULL){ 
            return false;
        }
        // B为NULL，返回false
        if(B == NULL)
            return false;
        bool *flag = malloc(sizeof(bool));
        *flag = false;
        dfs_A(A,B,flag);
        return *flag;
    }