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

题目

题目链接：
https://www.nowcoder.com/practice/4eaccec5ee8f4fe8a4309463b807a542

思路

深度优先搜索暴力匹配
思路和算法

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

参考答案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);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

参考答案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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

参考答案Go

package main

import . "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)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

参考答案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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47