另一棵树的子树

题目

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

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

提示：

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

刚开始看到题目，想到的思路是，从头开始遍历 root ，直到遍历到root->val与subRoot->val值相同时，开始同时遍历root 和 subRoot，如果直到遍历完subRoot，root->val与subRoot->val一直相同，则符合条件，返回true.如果在遍历完之前有不一样的值就从root的当前节点重新与subRoot开始比对。

在写完以上的代码进行测试时发现如果subRoot里面存在val相同的节点，那么可能会遗落一些情况。

如是开始重新思考思路，我们遍历root的每一个节点，然后在每一个节点和subRoot同时开始遍历，如果两者拥有相同的结构和值，就代表符合条件。

c++代码

判断两棵树是否具有的结构和值

function<bool(TreeNode*, TreeNode*)> dfs = [&](TreeNode* r, TreeNode* sub)->bool
{
	if (r == nullptr)
	{
		if (sub == nullptr)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	else
	{
		if (sub == nullptr)
		{
			return false;
		}
		else
		{
			if (r->val == sub->val)
			{
				return dfs(r->left, sub->left) && dfs(r->right, sub->right);
			}
			else
			{
				return false;
			}
		}
	}
};

遍历root

>function<bool(TreeNode*)> f = [&](TreeNode* r)->bool
		{
			if (r != nullptr)
			{
				if (dfs(r, subRoot))
				{
					return true;
				}
				else
				{
					return f(r->left) || f(r->right);
				}
			}
			else
			{
				return false;
			}
		};

看完题解后发现还有一种思路，就是按照前序遍历的顺序将root的值加入一个序列，并加入两个空值 lNull 和 rNull。同理将subRoot也同样输出一个前序遍历序列，如果subRoot是root的子树，则subRoot的序列是root的子序列。