另一棵树的子树

另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1：

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true
示例 2：

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

提示：

root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-104 <= root.val <= 104
-104 <= subRoot.val <= 104

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/subtree-of-another-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路1

朴素的解法就是找到root中的每棵子树，并比较两个子树是否相同。所以需要两个DFS的过程。第一个就是使用DFS比较两棵树是否相同。两棵树相同：节点值相同并且左右子树相同。还需要处理一下边界条件：两个根节点都是NULL，两个根节点都不是NULL以及其中一个根节点为NULL。第二个DFS就是遍历root的每一个子树并判断两棵树是否相同。最后的结果就是根节点的子树相同，或者右节点是子树或者左节点是子树。假设root的节点数目是s，subroot的节点数目是t,时间复杂度是\(O(s\times t)\),假设root的深度为d1,subRoot的深度为d2,空间复杂度就是max(d1,d2)。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

//我是真不擅长写树的递归算法啊！！！！
//先判断两棵树是否相同
//判断两棵树相同：节点值相同且左右子树相同
//边界条件的处理：两个都是NULL,两个都不是NULL,其中一个是NULL
//再DFS遍历所有子树并判断是否相同

class Solution {
public:

    bool same(TreeNode * root,TreeNode * subRoot)
    {
        if(root == NULL && subRoot == NULL) return true;
        else if(root != NULL && subRoot != NULL) return (root -> val == subRoot -> val) && same(root -> left,subRoot -> left) && same(root -> right, subRoot -> right);
        else return false;
    }

    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        
       bool t1,t2,t3;
       t1 = t2 = t3;
       if(root != NULL) t1 = same(root,subRoot);
       if(root -> left != NULL) t2 = isSubtree(root -> left,subRoot);
       if(root -> right != NULL) t3 = isSubtree(root -> right,subRoot);
       
       return t1 || t2 || t3;
    }
};

解题思路2 深度优先序列匹配

在最开始的时候考虑过，通过两棵树的先序遍历序列来判断两棵子树是否相同，也就是root的深度优先遍历的序列中是否存在subRoot的深度优先遍历。但是深度优先遍历结果相同一定能够推出树相同吗？其实不能啊。我们知道先序遍历是不能确定一个树的，得先序遍历+中序遍历才能确定一棵树，甚至先序遍历+后序遍历也不能确定一棵树。当然可以使用先序遍历+后序遍历是否存在子串作为判断结果，使用KMP算法作为子串的匹配算法。看了题解给出的方法，我们知道先序遍历不能确定一棵树的主要问题在于左右子节点有空值，并不是满的二叉树，比如2的左节点为1，1的右节点为2，为了使得先序遍历能够确定一个数，可以引入特定的值将树补满为满二叉树，也就是引入lNULL和rNULL,并使用KMP来判断子串。由于不会写KMP，先挖个坑，以后来补。