牛客NC98 判断t1树中是否有与t2树完全相同的子树【simple 深度优先dfs C++/Java/Go/PHP】

题目

在这里插入图片描述

在这里插入图片描述
题目链接：
https://www.nowcoder.com/practice/4eaccec5ee8f4fe8a4309463b807a542

思路

深度优先搜索暴力匹配
思路和算法这是一种最朴素的方法——深度优先搜索枚举
s 中的每一个节点，判断这个点的子树是否和
t 相等。如何判断一个节点的子树是否和
t 相等呢，我们又需要做一次深度优先搜索来检查，即让两个指针一开始先指向该节点和
t 的根，然后「同步移动」两根指针来「同步遍历」这两棵树，判断对应位置是否相等。

参考答案C++

/*** struct TreeNode {*  int val;*  struct TreeNode *left;*  struct TreeNode *right;*  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param root1 TreeNode类* @param root2 TreeNode类* @return bool布尔型*/bool isContains(TreeNode* root1, TreeNode* root2) {/*深度优先搜索暴力匹配思路和算法这是一种最朴素的方法——深度优先搜索枚举s 中的每一个节点，判断这个点的子树是否和t 相等。如何判断一个节点的子树是否和t 相等呢，我们又需要做一次深度优先搜索来检查，即让两个指针一开始先指向该节点和t 的根，然后「同步移动」两根指针来「同步遍历」这两棵树，判断对应位置是否相等。*/return dfs(root1, root2);}bool  dfs(TreeNode* s, TreeNode* t) {if (s == nullptr) return false;return check(s, t) || dfs(s->left, t) || dfs(s->right, t);}bool check(TreeNode* s, TreeNode* t) {if (s == nullptr && t == nullptr) return true;if (s == nullptr || t == nullptr || s->val != t->val)return false;return check(s->left, t->left) && check(s->right, t->right);}
};

参考答案Java

import java.util.*;/** public class TreeNode {*   int val = 0;*   TreeNode left = null;*   TreeNode right = null;*   public TreeNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param root1 TreeNode类* @param root2 TreeNode类* @return bool布尔型*/public boolean isContains (TreeNode root1, TreeNode root2) {/*深度优先搜索暴力匹配思路和算法这是一种最朴素的方法——深度优先搜索枚举s 中的每一个节点，判断这个点的子树是否和t 相等。如何判断一个节点的子树是否和t 相等呢，我们又需要做一次深度优先搜索来检查，即让两个指针一开始先指向该节点和t 的根，然后「同步移动」两根指针来「同步遍历」这两棵树，判断对应位置是否相等。*/return dfs(root1, root2);}public boolean dfs(TreeNode s, TreeNode t) {if (s == null) return false;return check(s, t) || dfs(s.left, t) || dfs(s.right, t);}public boolean check(TreeNode s, TreeNode t) {if (s == null && t == null) return true;if (s == null || t == null || s.val != t.val)return false;return check(s.left, t.left) && check(s.right, t.right);}
}

参考答案Go

package mainimport . "nc_tools"/** type TreeNode struct {*   Val int*   Left *TreeNode*   Right *TreeNode* }*//*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param root1 TreeNode类* @param root2 TreeNode类* @return bool布尔型*/
func isContains(root1 *TreeNode, root2 *TreeNode) bool {/*深度优先搜索暴力匹配思路和算法这是一种最朴素的方法——深度优先搜索枚举s 中的每一个节点，判断这个点的子树是否和t 相等。如何判断一个节点的子树是否和t 相等呢，我们又需要做一次深度优先搜索来检查，即让两个指针一开始先指向该节点和t 的根，然后「同步移动」两根指针来「同步遍历」这两棵树，判断对应位置是否相等。*/return dfs(root1, root2)
}func dfs(s, t *TreeNode) bool {if s == nil {return false}return check(s, t) || dfs(s.Left, t) || dfs(s.Right, t)
}func check(s, t *TreeNode) bool {if s == nil && t == nil {return true}if s == nil || t == nil || s.Val != t.Val {return false}return check(s.Left, t.Left) && check(s.Right, t.Right)
}

参考答案PHP

<?php/*class TreeNode{var $val;var $left = NULL;var $right = NULL;function __construct($val){$this->val = $val;}
}*//*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param root1 TreeNode类 * @param root2 TreeNode类 * @return bool布尔型*/
function isContains( $root1 ,  $root2 )
{/*深度优先搜索暴力匹配思路和算法这是一种最朴素的方法——深度优先搜索枚举s 中的每一个节点，判断这个点的子树是否和t 相等。如何判断一个节点的子树是否和t 相等呢，我们又需要做一次深度优先搜索来检查，即让两个指针一开始先指向该节点和t 的根，然后「同步移动」两根指针来「同步遍历」这两棵树，判断对应位置是否相等。*/return dfs($root1,$root2);
}function dfs($s,$t){if($s ==null) return false;return check($s,$t) || dfs($s->left,$t) || dfs($s->right,$t);
}function check($s,$t){if($s ==null && $t==null) return true;if($s ==null || $t==null || $s->val !=$t->val)return false;return check($s->left,$t->left) && check($s->right,$t->right);
}