剑指Offer-树的子结构(难)

发表于 | 分类于

题目描述

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

思路分析

思路参考《剑指Offer》一书。

1
2
3
4
5
6
7
8
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};

这道题，我不会，一点思路都没有，只能直接看答案了。。。 哎，还是要多多练练。要在树A中找到和树B的根节点的值一样的节点R；第二步，判断树A中以R为根节点的子树是不是包含和树B一样的结构。

第一步在树A中查找与根节点的值一样的节点，实际上就是树的遍历，采用递归的方式，对应代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        bool result = false; //检查空指针
        // 第一步在在树A中查找与根节点的值一样的节点
        if(pRoot1 && pRoot2){ //类似前序遍历
            if(pRoot1->val == pRoot2->val){
                result = IsSubtree(pRoot1, pRoot2);
            }
            if(!result){
                result = HasSubtree(pRoot1->left, pRoot2);
            }
            if(!result){
                result = HasSubtree(pRoot1->right, pRoot2);
            }
        }
        return result;
    }
};

在面试的时候，一定要注意边界条件的检查，即检查空指针。当树A或树B为空的时候，定义相应的输出。如果没有检查并进行相应的处理，则程序非常容易崩溃，这是面试的大忌。

在上述代码中，我们调用HasSubtree遍历二叉树A。如果发现某一节点的值和树B的头节点的值相同，则调用IsSubtree，进行第二步判断。

第二步是判断树A中以R为根节点的子树是不是和树B具有相同的结构。同样，也可以用递归的思路考虑：如果节点R的值和树B的根节点不相同，则以R为根节点的子树和树B肯定不同；如果值相同，则递归地判断他们各自的左右节点的值是不是相同。递归的终止条件是我们到达了树A或者树B的节点。对应代码如下：

1
2
3
4
5
6
bool IsSubtree(TreeNode* p1, TreeNode* p2){
    if(p2 == NULL) return 0;
    if(p1 == NULL && p2) return 0;
    if(p1->val != p2->val) return 0;
    return IsSubtree(p1->left, p2->left) & IsSubtree(p1->right, p2->right);
}

上述代码有多处判断一个指针是不是空，这样做是为了避免试图访问空指针而造成陈旭崩溃，同时也设置了递归调用的退出条件。在写遍历树的代码时要高度警惕，在每一处需要访问地址的时候询问自己这个地址有没有可能是NULL，如果是该如何。

若树的结构中val的类型是double，则不能用==直接判断相等，而要设置如下判断函数：

1
2
3
4
5
6
bool Equal(double num1, double num2){
    if ((num1-num2 > -0.0000001) && (num1-num2 < 0.0000001))
        return true;
    else 
        return false;
}