《剑指offer刷题笔记》25、树的子结构【c++详细题解】

àì夳堔傛蜴生んèń 2021-07-24 18:23 317阅读 0赞

### **题目** ###

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

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

**样例**

树 A：

8
        / \
       8   7
      / \
     9   2
        / \
       4   7

树 B：

8
      / \
     9   2

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

### **思路** ###

**(二叉树，递归)**  O ( n m ) O(nm) O(nm)  
代码分为两个部分：

1.  遍历树A中的所有非空节点R；
2.  判断树A中以R为根节点的子树是不是包含和树B一样的结构，且我们从根节点开始匹配；

对于第一部分，我们直接递归遍历树A即可，遇到非空节点后，就进行第二部分的判断。

**对于第二部分，我们同时从根节点开始遍历两棵子树：**

*  如果树B中的节点为空，则表示当前分支是匹配的，返回true；
 *  如果树A中的节点为空，但树B中的节点不为空，则说明不匹配，返回false；
 *  如果两个节点都不为空，但数值不同，则说明不匹配，返回false；
 *  否则说明当前这个点是匹配的，然后递归判断左子树和右子树是否分别匹配即可；

**时间复杂度**  
最坏情况下，我们对于树A中的每个节点都要递归判断一遍，每次判断在最坏情况下需要遍历完树B中的所有节点。  
所以时间复杂度是  O ( n m ) O(nm) O(nm)，其中  n n n树A中的节点数，  m m m 是树B中的节点数。

### **代码** ###

/** * 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; //如果A或者B树一个为空，返回false
            if(isSame(pRoot1,pRoot2)) return true;//从根节点开始匹配
            //如果从根节点开始不匹配的话，我们递归到A的左右子树去匹配
            if(hasSubtree(pRoot1->left,pRoot2)||hasSubtree(pRoot1->right,pRoot2)) return true;
        }
        bool isSame(TreeNode* pRoot1, TreeNode* pRoot2)
        { 
            if(!pRoot2) return true; //B树为空，匹配成功，递归结束的终点
            if(!pRoot1 || pRoot1->val!=pRoot2->val) return false;
            //否则说明当前这个点是匹配的，然后递归判断左子树和右子树是否分别匹配即可
            return isSame(pRoot1->left,pRoot2->left)&&isSame(pRoot1->right,pRoot2->right);
        }
    };