算法14.树的子结构 |

二叉树递归

算法

发布日期: 2020-10-27

更新日期: 2020-10-27

文章字数: 570

阅读次数:

题目描述

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

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

示例 1：

给定的树 A:

     3
    / \
   4   5
  / \
 1   2
给定的树 B：
   4 
  /
 1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 2：

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

解题思路

方法一：普通分析

时间复杂度：$O(MN)$

空间复杂度：$O(M)$

代码如下

class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A==NULL || B==NULL) return false;
        if(A->val == B->val) return reverse(A,B) || isSubStructure(A->left,B) || isSubStructure(A->right,B);
        if(A->val != B->val) return isSubStructure(A->left,B) || isSubStructure(A->right,B);
        return false;
    }
    bool reverse(TreeNode *A,TreeNode *B){
        if(B==NULL) return true;
        if(A==NULL || A->val!=B->val)   return false;
        return reverse(A->left,B->left) && reverse(A->right,B->right);
    }
};

解法分析

要找到匹配的子树，首先头结点需要首先匹配。所以需要遍历$A$子树，寻找头结点匹配的子树。

需要找合适的头结点之后，接着对该头结点下面形成的树和$B$子树进行匹配。双重递归！

匹配过程是在$reverse$函数中进行，具体如下：

终止条件
当节点 $B$ 为空：说明树 $B$ 已匹配完成（越过叶子节点），因此返回 $true$ ；
当节点 $A$ 为空：说明已经越过树 $A$ 叶子节点，即匹配失败，返回 $false$ ；
当节点 $A$ 和 $B$ 的值不同：说明匹配失败，返回 $false$ ；
返回值
判断 $A$ 和 $B$ 的左子节点是否相等，即 $recur(A.left, B.left)$ ；
判断 $A$ 和 $B$ 的右子节点是否相等，即 $recur(A.right, B.right)$ ；

而主函数的返回值必须满足以下三种情况之一：