【JZ26 树的子结构】

描述

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

（我们约定空树不是任意一个树的子结构）
假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构

数据范围:
0 <= A的节点个数 <= 10000
0 <= B的节点个数 <= 10000

示例1

输入： {8,8,7,9,2,#,#,#,#,4,7},{8,9,2}

返回值：true

示例2

输入： {1,2,3,4,5},{2,4}

返回值：true

示例3

输入： {1,2,3},{3,1}

返回值：false

C++，剑指Offer原书代码详解

先在树A中找到值为树B根节点的值的节点，然后判断这个节点的子树是否含有和树B一样的结构。

1. 第一步中，查找与根节点值一样的节点，采用递归的方法来遍历树。
   

   
   

2. 第二步中，同样采用递归的方法，判断判断当前对应节点是否相同，然后递归判断左、右节点，递归终止条件是到达了叶节点。
   

   
   

class Solution {
public:
    bool DoesTree1HaveTree2(TreeNode* pRoot1, TreeNode* pRoot2){
        if(pRoot2 == nullptr)
            return true;
        if(pRoot1 == nullptr)
            return false;
        if(!(pRoot1->val==pRoot2->val))
            return false;
        return DoesTree1HaveTree2(pRoot1->left, pRoot2->left) &&
        DoesTree1HaveTree2(pRoot1->right, pRoot2->right);
    }
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        bool result = false;
         
        if(pRoot1 != nullptr && pRoot2 != nullptr)
        {
            if(pRoot1->val==pRoot2->val)
                result = DoesTree1HaveTree2(pRoot1, pRoot2);
            if(!result)
                result = HasSubtree(pRoot1->left, pRoot2);
            if(!result)
                result = HasSubtree(pRoot1->right, pRoot2);
        }      
        return result;
    }
};

运行时间：8ms
超过0.98% 用C++提交的代码
占用内存：1420KB
超过15.05%用C++提交的代码