subTree

发表于 分类于

题目描述[原题链接][https://www.acwing.com/problem/content/description/35/]

输入两棵二叉树A，B，判断B是不是A的子结构。

我们规定空树不是任何树的子结构。

样例

树A：

1
2
3
4
5
6
7
    8
   / \
  8   7
 / \
9   2
   / \
  4   7

树B：

1
2
3
  8
 / \
9   2

返回 true ,因为B是A的子结构。

算法描述

题目的意思就是找到树A中的子结构树B，首先需要一个子函数用来判断两子树是否相等，用递归实现，再对每个节点排查，找到了满足条件的结构输出true，没有输出false;要注意的就是成立条件，当子结构的节点为空的时候返回true，节点值不相等返回false

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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 hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if(!pRoot1||!pRoot2)return false;
        if(judge(pRoot1,pRoot2))return true;
        return hasSubtree(pRoot1->left,pRoot2)||hasSubtree(pRoot1->right,pRoot2);
    }
    
    bool judge(TreeNode* p1,TreeNode* p2){
        if(!p2)return true;
        if(!p1||p1->val!=p2->val)return false;
        return judge(p1->left,p2->left)&&judge(p1->right,p2->right);
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean hasSubtree(TreeNode pRoot1, TreeNode pRoot2) {
        if(pRoot1==null||pRoot2==null)return false;
        if(judge(pRoot1,pRoot2))return true;
        return hasSubtree(pRoot1.left,pRoot2)||hasSubtree(pRoot1.right,pRoot2);
        
    }
    
    public boolean judge(TreeNode p,TreeNode q){
        if(q==null)return true;
        if(p==null||p.val!=q.val)return false;
        return judge(p.left,q.left)&&judge(p.right,q.right);
    }
}