572. Subtree of Another Tree

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself.

帮助方法isEqual,DFS搜索判断两个节点的子节点是否完全相同。
DFS搜索,如果两个根节点的值相等则返回,且调用isEqual方法,如果子节点都相同则返回。

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
return dfs(root, subRoot) != null;
}

private TreeNode dfs(TreeNode root, TreeNode subRoot){
if(root == null) return null;
if(root.val == subRoot.val && isEqual(root, subRoot)) return root;
if(dfs(root.left, subRoot) != null ) return dfs(root.left, subRoot);
else return dfs(root.right, subRoot);
}

private boolean isEqual(TreeNode root, TreeNode subRoot){
if(root == null || subRoot == null) return root == subRoot;
if(root.val != subRoot.val) return false;
return isEqual(root.left, subRoot.left) && isEqual(root.right, subRoot.right);
}
}
Author

Xander

Posted on

2022-04-22

Updated on

2022-04-21

Licensed under

Comments