剑指 Offer 26. 树的子结构

剑指 Offer 26. 树的子结构 - 力扣（LeetCode）

附对称性递归总结：

一篇文章带你吃透对称性递归(思路分析+解题模板+案例解读) - 树的子结构 - 力扣（LeetCode）

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

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

例如:
给定的树 A:

 3
/ \
4   5
  / \
 1   2

给定的树 B：

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

思路：

---

对称性递归 一个函数将问题拆分为 遍历A树每个节点作为B树根节点

一个函数处理上一个函数提出的问题 检查每种可能的结果

复杂度：

O(n*n)（应该吧，递归算不明白）

题解：

class Solution {
public:
    bool fnc(TreeNode* A, TreeNode* B){//这个函数执行：判断分别以A，B为根节点的树，B树是否为A树的子结构
        if(!B)
            return true;//证明A树完全包括B树
        if(!A)
            return false;//证明至少有一部分B树无法被A树包括
        return (A->val==B->val)&&fnc(A->right,B->right)&&fnc(A->left,B->left);//val数值相同观察子树
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {//这个函数执行：判断以B为根节点的树是否为A树的一部分，区别在于A树不必为根节点，A树的子树也可
        return (A&&B)&&(fnc(A,B)||isSubStructure(A->left,B)||isSubStructure(A->right,B));
    }//第一个条件判断特例 A和B都必须为非空
     //以A为根节点，或者存在于A树左右儿子中
};