題目：輸入兩棵二叉樹A弱贼，B蒸苇，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹不是任意一個樹的子結(jié)構(gòu)）
練習(xí)地址
https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88
https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/
參考答案
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public boolean HasSubtree(TreeNode root1, TreeNode root2) {
if (root1 == null || root2 == null) {
return false;
}
if (isSubtree(root1, root2)) {
return true;
}
return HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
}
private boolean isSubtree(TreeNode root1, TreeNode root2) {
if (root2 == null) {
return true;
}
if (root1 == null) {
return false;
}
if (root1.val != root2.val) {
return false;
}
return isSubtree(root1.left, root2.left) && isSubtree(root1.right, root2.right);
}
}
復(fù)雜度分析
- 時間復(fù)雜度：O(mn)吮旅。
- 空間復(fù)雜度：O(n)溪烤。
