一、题目

限制：0 <= 节点个数 <= 10000

二、思路

题目判断的是B是否为A树的【子结构】，而不判断是【子树】。

直观的思路：

• 从A的每个节点开始逐个（递归）遍历，（假设当前的节点为K）；
• 然后判断B树，是否为当前以K节点为头结点的子结构。

上面第二步，对应下面代码的issame部分：

• 如果B树为空（先遍历完了），则是子结构；
• 如果B树不空，A树为空（A树先遍历完了），则不是子结构；
• AB树当前节点都不空了，但是val不相同，也不是子结构了；
• AB树当前节点都不空，并且val相同（暂时满足），继续分别递归A和B的左子树、右子树。

三、代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        //约定空树不是任意一个树的子结构
        if(!A || !B) return false;
        //第二部分
        if(issame(A, B)) return true;
        return isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
    bool issame(TreeNode* a, TreeNode* b){
        if(!b) return true;
        if(!a) return false;
        if(a->val != b->val) return false;
        //两棵子树的当前节点相同，递归遍历
        return issame(a->left, b->left) && issame(a->right, b->right);
    }
};

  

 

  
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
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/123743424