树的子结构

题目描述：

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

解题思路

看的树的题目可以从递归的角度考虑问题

1. 先找到树的根结点，如果大树的根结点与小树的根结点相等，则进而判断大叔是否从这个结点开始包含小树
2. 如果不相等，则继续递归的看大树的左子树，以及大树的右子树

代码

#include <iostream>
using namespace std;

class Solution {
public:
    bool HasSubtree(TreeNode *pRoot1, TreeNode *pRoot2) {
        // 定义一个变量，储存结果
        bool result = false;

        // 判断边界条件
        if (pRoot1 == NULL || pRoot2 == NULL) 
            return false;

        // 如果两个树都不是空树,并且树根的值相等
        if (pRoot1->val == pRoot2->val) {
            result = DoesTree1HasTree2(pRoot1, pRoot2);
        }
        // 如果上面发现小树不是大树的子树，则继续看小树是不是大树的左子树的sub tree
        if (!result) {
            result = HasSubtree(pRoot1->left, pRoot2);
        }
        if (!result) {
            result = HasSubtree(pRoot1->right, pRoot2);
        }

        return result;
    }
private:
    // DoesTree1HasTree2这个函数用来判断当两个树的树根相等的时候，其下方的子树是否相等
    bool DoesTree1HasTree2(TreeNode *root1, TreeNode *root2) {
        bool result;
        // 第一次进入此函数的时候，root1的值和root2的值必然是相等的
        // root2也一定是非空的
        if (root2 == NULL)
            return true;

        // 如果root2不是空，但是root1已经为空了
        // 则说明root2包含了root1没有的元素
        // 故小树不是大树的sub tree
        if (root1 == NULL)
            return false;

        // 上面的两个if条件保证了，root1和root2都不是NULL
        // 此时比较一下两个结点的数值，如果相等则继续
        // 如果不等则说明不是子树，返回false
        if (root1->val != root2->val) {
            return false;
        }

        // 如果进行到了这个步骤，则说明前三个if都不成立，即：
        // root1不是NULL，root2不是NULL，root1和root2的值相等
        // 则继续比较root1和root2的左右子树
        // 若都返回真则说明小树是大树的sub tree
        result = DoesTree1HasTree2(root1->left, root2->left) && DoesTree1HasTree2(root1->right, root2->right);
        return result;
    }
};

// 通过HasSubtree函数来找到两个树相同的根结点
// 当找到了相同的根结点之后，用DoesTree1HasTree2函数来对小树和大树深入的比较

2018.10.10