文章目錄
- 題目
- 分析
- 代碼
題目
輸入兩棵二叉樹A，B，判斷B是不是A的子結構，（ps：我們約定空樹不是任意一個樹的子結構）
分析
- 先序遍歷樹 A中的每個節點node1
- 判斷樹A中以node1為根節點的子樹是否包含樹B
終止條件：
- 當節點 node2為空：說明樹B已匹配完成（越過葉子節點），因此回傳 true
- 當節點 node1 為空：說明已經越過樹 A葉子節點，即匹配失敗，回傳 false
- 當節點 node1和 node2 的值不同：說明匹配失敗，回傳 false
判斷 A 和 B 的左子節點是否相等
判斷 A 和 B 的右子節點是否相等
代碼
public boolean HasSubtree(TreeNode root1, TreeNode root2) {
if (root1 == null || root2 == null) return false;
return HasSubtree2(root1, root2) || HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);
}
public boolean HasSubtree2(TreeNode node1, TreeNode node2) {
if (node2 == null) return true;
if (node1 == null || node1.val != node2.val) return false;//node2還不為空
return HasSubtree2(node1.left, node2.left) && HasSubtree2(node1.right, node2.right);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/254930.html
標籤：java
上一篇：服務介面呼叫：OpenFeign