題目描述

輸入兩棵二叉樹A，B，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹不是任意一個樹的子結(jié)構(gòu)）

解決方案：

/** 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) {boolean result = false;//當Tree1和Tree2都不為零的時候，才進行比較。否則直接返回falseif (root2 != null && root1 != null) {//如果找到了對應Tree2的根節(jié)點的點if(root1.val == root2.val){//以這個根節(jié)點為為起點判斷是否包含Tree2result = doesTree1HaveTree2(root1,root2);}//如果找不到，那么就再去root的左兒子當作起點，去判斷時候包含Tree2if (!result) {result = HasSubtree(root1.left,root2);}//如果還找不到，那么就再去root的右兒子當作起點，去判斷時候包含Tree2if (!result) {result = HasSubtree(root1.right,root2);}}//返回結(jié)果return result;}public boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2) {//如果Tree2已經(jīng)遍歷完了都能對應的上，返回trueif (node2 == null) {return true;}//如果Tree2還沒有遍歷完，Tree1卻遍歷完了。返回falseif (node1 == null) {return false;}//如果其中有一個點沒有對應上，返回falseif (node1.val != node2.val) { return false;}//如果根節(jié)點對應的上，那么就分別去子節(jié)點里面匹配return doesTree1HaveTree2(node1.left,node2.left) && doesTree1HaveTree2(node1.right,node2.right);} }

總結(jié)

以上是生活随笔為你收集整理的剑指offer 树的子结构的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。