国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

劍指offer：樹的子結構（Java）

taoszu / 2523人閱讀

摘要：問題描述輸入兩棵二叉樹，，判斷是不是的子結構。調用方法判斷是不是的子結構當前兩個根節點的值不相等就判斷的左子節點是否和節點相等的左子樹的節點都和不等的情況下判斷的右子樹節點和是不是相等。

1.問題描述

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

2.思路

首先根據題目，只有兩個樹都不為null時才需要進行判斷，否則直接返回false。
然后就是遍歷大樹，找小樹的頭節點，如果遍歷完都沒找到，就是false
如果找到小樹的頭節點，就依次比較后面對應的左右子節點，如果有一個不相等就是false，
一一對應到最后時，肯定是小樹的節點為null，大樹不一定為null，所以先用小樹判斷。
如果大樹為null了，小樹還不是，說明小樹不是大樹的子結構，返回false。

我覺得難的是遍歷大樹過程中左子樹遍歷完成后如何回到根節點，這里使用兩個方法，在第二個方法中進行遞歸遍歷根節點一側的子樹，遍歷完成后就可以再第一個方法中返回到根節點了。

/**
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;    //用來記錄判斷結果
        if(root1 != null && root2 != null){    //只有兩個根節點都不為null時才進行判斷，否則直接返回false。
                result = doesTree1HaveTree2(root1,root2);    //調用doesTree1HaveTree2方法判斷Tree2是不是Tree1的子結構
            if(!result){    //當前兩個根節點的值不相等就判斷root1的左子節點是否和root2節點相等
                result = doesTree1HaveTree2(root1.left,root2);
            }
            if(!result){    //root1的左子樹的節點都和root2不等的情況下判斷root1的右子樹節點和root2是不是相等。
                result = doesTree1HaveTree2(root1.right, root2);
            }
        }
        return result;    //root1都遍歷完成后返回結果。
    }
    
    public boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2){
        if(node2 == null){    //如果node2樹先遍歷完了都和node1對上，說明node2是node1的子結構返回true
            return true;
        }
        if(node1 == null){    //如果node2不為null而node1為null了說名node2不是node1的子結構，返回false
            return false;
        }
        if(node1.val != node2.val){    //只要判斷過程中有一個不想等直接返回false，這里注意只是判斷一個子樹沒有匹配的，在HasSubTree中還會判斷右子樹中是否存在root2結構，所以不會漏掉。
            return false;
        }
        return doesTree1HaveTree2(node1.left, node2.left) && doesTree1HaveTree2(node1.right, node2.right);
        //當前節點的值相等，判斷左右兩個子節點的值是不是相等，有一個不等就返回false。
    }
}

注意：

(1)doesTree1HaveTree2方法中判斷小樹是否為null必須放在前面，不能和判斷大樹是否為null交換，因為如果換了的話，在大樹為null時，小樹不確定，小樹如果也為null，就應該是true，而這時返回的是false，就是錯誤的。
(2)如果根節點的左子樹中有小樹的一部分，而右子樹中有整個小樹，這種情況不會漏掉，因為在HasSubTree方法中是先判斷左子樹，在判斷右子樹，左子樹返回false時，會在右子樹中重新找小樹的根節點，所以不會漏掉。

參考
Boooobby的牛客網答案

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/75533.html

相關文章

  • 【劍指offer】5.二叉樹的鏡像和打印

    摘要：題目二叉樹的鏡像題目描述操作給定的二叉樹，將其變換為源二叉樹的鏡像。代碼題目從上往下打印二叉樹題目描述從上往下打印出二叉樹的每個節點，同層節點從左至右打印。解題思路借助隊列先進先出的數據結構讓二叉樹每層依次進入隊列依次打印隊列中的值代碼 二叉樹簡介 基本結構： function TreeNode(x) { this.val = x; this.left = null; ...

    villainhr 評論0 收藏0

  • 從簡歷被拒到收割今日頭條 offer，我用一年時間破繭成蝶！

    摘要：正如我標題所說，簡歷被拒。看了我簡歷之后說頭條競爭激烈，我背景不夠，點到為止。。三準備面試其實從三月份投遞簡歷開始準備面試到四月份收，也不過個月的時間，但這都是建立在我過去一年的積累啊。 本文是 無精瘋 同學投稿的面試經歷 關注微信公眾號：進擊的java程序員K，即可獲取最新BAT面試資料一份 在此感謝 無精瘋 同學的分享 目錄： 印象中的頭條 面試背景 準備面試 ...

    tracymac7 評論0 收藏0

  • 從簡歷被拒到收割今日頭條 offer，我用一年時間破繭成蝶！

    摘要：正如我標題所說，簡歷被拒。看了我簡歷之后說頭條競爭激烈，我背景不夠，點到為止。。三準備面試其實從三月份投遞簡歷開始準備面試到四月份收，也不過個月的時間，但這都是建立在我過去一年的積累啊。 本文是 無精瘋 同學投稿的面試經歷 關注微信公眾號：進擊的java程序員K，即可獲取最新BAT面試資料一份 在此感謝 無精瘋 同學的分享目錄：印象中的頭條面試背景準備面試頭條一面（Java+項目）頭條...

    wdzgege 評論0 收藏0

  • PHPer面試必看：分門別類帶你擼《劍指Offer》之二叉樹

    摘要：例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹并返回。操作給定的二叉樹，將其變換為源二叉樹的鏡像。劍指中還有一道類似的變種題目，就是下面的這道，之字形遍歷二叉樹。最后下面的兩道題目分別運用了二叉樹先序中序遍歷算法。 開篇 以下內容可能偏應試但很好理解，所以大家一定要堅持看下去，因為我們變強的過程注定孤獨的，堅持下來就會看到明天的太陽。 回顧 showImg(https://user-...

    li21 評論0 收藏0

  • Java實現基本數據結構2（樹）

    摘要：實現基本數據結構棧，隊列，鏈表這篇筆記側重點二叉樹的三種遍歷前中后迭代非迭代代碼重建二叉樹的代碼與分析和關于二叉樹的題簡單理解二叉查找樹紅黑樹，的性質，實際用途。同時，以對應的節點為邊界，就會把中序遍歷的結果分為左子樹和右子樹。 雖是讀書筆記，但是如轉載請注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復制黨 以下是算法導論第十...

    opengps 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<