一、題目大意
給你兩棵二叉樹 root 和 subRoot ，檢驗 root 中是否包含和 subRoot 具有相同結構和節點值的子樹，如果存在，回傳 true ；否則，回傳 false ，
二叉樹 tree 的一棵子樹包括 tree 的某個節點和這個節點的所有后代節點，tree 也可以看做它自身的一棵子樹，
示例 1：
輸入：root = [3,4,5,1,2], subRoot = [4,1,2]
輸出：true
示例 2：
輸入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
輸出：false
提示：
-
root 樹上的節點數量范圍是 [1, 2000]
-
subRoot 樹上的節點數量范圍是 [1, 1000]
-
-104 <= root.val <= 104
-
-104 <= subRoot.val <= 104
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/subtree-of-another-tree
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
二、解題思路
思路1:子樹必須是從葉節點開始的，中間部分的不能算是子樹，轉換一下思路，從root的某個節點開始，就跟subRoot的所有結構都一樣，那么問題就轉換成了判斷兩棵樹是否相同
思路2:對root和subRoot兩棵樹分別進行序列化，各生成一個字串，如果subRoot的字串是root的子串的話，說明subRoot是s的子樹，需要注意的是，在序列化的時候要特殊處理一下，就是在每個節點前面都加上一個字符，比如,,那么12序列化后就是,12,#2序列化后就是,2,#
三、解題方法
3.1 Java實作
public class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
// root至少有1個節點
// subRoot至少有1個節點
if (root == null) {
return false;
}
boolean isSame = isSameTreeNode(root, subRoot);
if (isSame) {
return true;
}
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
boolean isSameTreeNode(TreeNode node1, TreeNode node2) {
if (node1 == null && node2 == null) {
return true;
}
if (node1 == null && node2 != null) {
return false;
}
if (node1 != null && node2 == null) {
return false;
}
if (node1.val != node2.val) {
return false;
}
return isSameTreeNode(node1.left, node2.left) && isSameTreeNode(node1.right, node2.right);
}
}
四、總結小記
- 2022/9/28 雖然很簡單，但是看到通過的那一刻還是很開心的
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/509785.html
標籤：其他
上一篇：WEB自動化-11-資料驅動