0%

树的子结构

发表于 更新于

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

从根开始完全相等(is)，或在左、右子树(has)。

对于相等(is)，同时遍历。
对于存在(has)，遍历树A。

综上：

  1. 遍历树A
    1. 若A的当前节点与B的根一致
      2. 遍历树B

递归或队列（层次遍历）或栈（前序、中序、后续）均可。

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
32
33
34
35
36
37
38
39
40
41
42
/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    bool IsSubtree(const TreeNode const * pRoot1, const TreeNode const * pRoot2)
    {
        if (pRoot2 == nullptr)
        {
            return true;
        }
        else if (pRoot1 == nullptr)
        {
            return false;
        }
        else
        {
            return pRoot1->val == pRoot2->val && \
                IsSubtree(pRoot1->left, pRoot2->left) && \
                IsSubtree(pRoot1->right, pRoot2->right);
        }
    }
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        if (pRoot1 == nullptr || pRoot2 == nullptr)
        {
            return false;
        }
        else
        {
            return IsSubtree(pRoot1, pRoot2) || \
                HasSubtree(pRoot1->right, pRoot2) || \
                HasSubtree(pRoot1->left, pRoot2);
        }
    }
};