《剑指offer》 26. 树的子结构

剑指offer
留言

note:递归是一般求解二叉树问题最常用的手段，做好特殊判断、找到递归终止条件，写好递归体，就可以解决此类问题

题目描述

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

1
2
3
4
5
	 3
/ \
  4   5
 / \
1   2

给定的树 B：

1
2
3
  4 
 /
1

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

1
2
输入：A = [1,2,3], B = [3,1]
输出：false

示例 2：

1
2
输入：A = [3,4,5,1,2], B = [4,1]
输出：true

限制：

1
0 <= 节点个数 <= 10000

方法：双递归解题

思路

这道题要求找树的子结构，注意是要求结构相同，那么就不能简单的想着用某种遍历手段，然后判断遍历生成的字符串是否是子串这种思路来解题（这是我一开始犯下的错误）。因为要求的结构相同，单单看遍历串其实很容易出现一些巧合，导致不在一棵子树上的节点被误以为在一个节点上，从而误以为结构相同。

所以这道题应该在每一步都考虑具体的结构。所以采用两个递归函数，其中一个递归函数来判断二叉树B在当前节点的左子树还是右子树上，另一个递归函数则是判断结构是否相同。

第一个递归函数isSubStructure函数

用来遍历树A。

递归终止条件：根绝题意，空节点不构成子树，所以我们可以把递归终止条件设置为两个节点中有一个节点为空节点。

递归行为：根据前文分析，大致有三种情况

  • 树B是和当前子树的结构相同。
  • 树B和当前子树的左子树结构相同
  • 树B和当前子树的右子树结构相同

返回值：三种递归结果的或运算

第二个递归函数dfs函数

用来遍历树B，看B的结构是否等于A的子树。

递归终止条件:

  • 遍历B子树的指针为空时，说明前面的父节点都相同，可以返回true，表示这一支为真
  • 遍历A子树的指针为空，但是B子树的指针还没有为空，则说明结构不同，返回false
  • 遍历AB两棵树，如果当前节点不相同，则说明结构不同返回false

递归行为

显然，我需要分别递归左右子树看是否结构完全相同

返回值：

递归左右子树都得到返回值为真，才说明这个子树是结构相同的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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 {
    bool dfs(TreeNode* A, TreeNode *B){
        if(B==NULL)
            return true;
        else if(A==NULL || A->val!=B->val)
            return false;
        return dfs(A->left,B->left) && dfs(A->right,B->right);
    }
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A==NULL || B==NULL)
            return false;
        return dfs(A,B) || isSubStructure(A->left,B) || isSubStructure(A->right,B);
    }
};

复杂度分析

  • 时间复杂度$O(MN)$.其中M，N分别为两棵子树的节点数。显然我们首先遍历了树A，时间复杂度应该为$O(M)$，然后在每层递归中遍历了树B，所以复杂度为O(N)。最终时间复杂度即为$O(MN)$
  • 空间复杂度$O(M)$.虽然我们需要遍历到每个子树的各个节点，但是显然当我们在遍历子树A时，随着递归栈的深入，对另一个递归函数的调用，结束的也越快（因为一但A的节点为空节点，就会马上返回，释放递归栈空间）。所以最终空间复杂度为$O(M)$。