文章目錄

• 題目描述
• 思路 & 代碼
• • • 二刷

題目描述

• 思路很值得看的一道題，和之前路徑總和 III的雙遞歸思路、結構很像
  

思路 & 代碼

• isSubStructrue() 進行一個前序的遍歷；通過 || 運算符，在找到時直接終止遍歷
• 具體函數功能、思路見代碼注釋

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/ class Solution {// 函數功能：遍歷，判斷 B 是否為 A 的子結構public boolean isSubStructure(TreeNode A, TreeNode B) {// 空樹不是任意一個樹的子結構if(A == null || B == null){return false;}// 先序：以 A 開始的子結構判斷 || 左節點繼續遍歷 || 右節點繼續遍歷return recursion(A, B) || isSubStructure(A.left, B) || isSubStructure (A.right, B);}// 函數功能：判斷以A開始的樹，是否包含子結構B樹。boolean recursion(TreeNode A, TreeNode B){// B遍歷結束，說明完全覆蓋了B，子結構if(B == null){return true;}// A遍歷結束 or 節點值不同：不是子結構if(A == null || A.val != B.val){return false;}// 當前節點相同，繼續進行左右子數的判斷return recursion(A.left, B.left) && recursion(A.right, B.right);} }

二刷

• 二刷居然忘了思路了= =
• 先對當前A，B進行符合判斷，不行的話就再對A.left && B、A.right && B 進行判斷。以此類推
• isStructure() 是直接對當前節點進行判斷

class Solution {public boolean isSubStructure(TreeNode A, TreeNode B) {if(A == null || B == null) {return false;}return isStructure(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);}public boolean isStructure(TreeNode A, TreeNode B) {if(B == null) {return true;}if(A == null || A.val != B.val) {return false;}return isStructure(A.left, B.left) && isStructure(A.right, B.right);} }

總結

以上是生活随笔為你收集整理的【LeetCode笔记】剑指 Offer 26-. 树的子结构 （Java、双重dfs、二刷）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。