【刷算法】一棵樹是否是另一棵樹的子結(jié)構(gòu)

Chaz 發(fā)布于2019-08-26 12:09 / 2066人閱讀

題目描述

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

分析

假設(shè)樹A的根節(jié)點(diǎn)ra和樹B的根節(jié)點(diǎn)rb值相同，那么接下來就以這兩個(gè)節(jié)點(diǎn)開始依次比較ra.left和rb.left、ra.right和rb.right，過程中只要有一個(gè)不相同則返回；繼續(xù)比較ra.left和rb是否相同、ra.right和rb是否相同，就這樣依次進(jìn)行下去，時(shí)間復(fù)雜度則為O(樹A的節(jié)點(diǎn)數(shù))*O(樹B的節(jié)點(diǎn)數(shù))

代碼實(shí)現(xiàn)

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function HasSubtree(r1, r2)
{    
    if(r1 === null || r2 === null)
        return false;
    return check(r1, r2) || HasSubtree(r1.left, r2) || HasSubtree(r1.right, r2);
}
function check(a,b){
    if(b === null)
        return true;
    if(a === null || a.val !== b.val)
        return false;
    return check(a.left, b.left) && check(a.right, b.right);
}

云服務(wù)器 GPU云服務(wù)器一棵樹用c語(yǔ)言打出一棵樹棵樹一棵

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/108115.html

相關(guān)文章

?算法入門?《二叉樹 - 二叉搜索樹》簡(jiǎn)單05 —— LeetCode 897. 遞增順序搜索樹

文章目錄一、題目1、題目描述2、基礎(chǔ)框架3、原題鏈接二、解題報(bào)告1、思路分析2、時(shí)間復(fù)雜度3、代碼詳解三、本題小知識(shí)四、加群須知一、題目 1、題目描述 ??給你一棵二叉搜索樹，請(qǐng)按中序遍歷將其重新排列為一棵遞增順序搜索樹，使樹中最左邊的節(jié)點(diǎn)成為樹的根節(jié)點(diǎn)，并且每個(gè)節(jié)點(diǎn)沒有左子節(jié)點(diǎn)，只有一個(gè)右子節(jié)點(diǎn)。??樣例輸入： [5,3,6,2,4,null,8,1,null,null,nu...

Soarkey 2021-09-10 10:51 評(píng)論0 收藏0
【刷算法】二叉搜索樹與雙向鏈表

摘要：題目描述輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹中結(jié)點(diǎn)指針的指向。題目描述輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹中結(jié)點(diǎn)指針的指向。分析如果是這樣一棵二叉搜索樹： showImg(https://segmentfault.com/img/remote/14600000...

FreeZinG 2019-08-22 18:32 評(píng)論0 收藏0
js 中二叉樹的深度遍歷與廣度遍歷(遞歸實(shí)現(xiàn)與非遞歸實(shí)現(xiàn))

摘要：樹中結(jié)點(diǎn)的最大層次稱為樹的深度或高度。二叉樹有深度遍歷和廣度遍歷，深度遍歷有前序中序和后序三種遍歷方法。二叉樹的前序遍歷可以用來顯示目錄結(jié)構(gòu)等中序遍歷可以實(shí)現(xiàn)表達(dá)式樹，在編譯器底層很有用后序遍歷可以用來實(shí)現(xiàn)計(jì)算目錄內(nèi)的文件及其信息等。樹的簡(jiǎn)介棧、隊(duì)列、鏈表等數(shù)據(jù)結(jié)構(gòu)，都是順序數(shù)據(jù)結(jié)構(gòu)。而樹是非順序數(shù)據(jù)結(jié)構(gòu)。樹型結(jié)構(gòu)是一類非常重要的非線性結(jié)構(gòu)。直觀地，樹型結(jié)構(gòu)是以分支關(guān)系定義的層次結(jié)...

Yuanf 2019-08-23 11:38 評(píng)論0 收藏0
【React進(jìn)階系列】虛擬dom與diff算法

摘要：通過對(duì)樹進(jìn)行層級(jí)控制，同一個(gè)父節(jié)點(diǎn)下的所有子節(jié)點(diǎn)。新老集合進(jìn)行差異化對(duì)比，發(fā)現(xiàn)，則創(chuàng)建并插入至新集合，刪除老集合以此類推，創(chuàng)建并插入和，刪除和。虛擬dom Jsx 表面寫的是html，其實(shí)內(nèi)部執(zhí)行的是一段js createElement React.createElement( type, [props], [...children] ) createElement把這個(gè)...

zhou_you 2019-08-23 12:24 評(píng)論0 收藏0
【刷算法】求二叉樹深度的遞歸以及非遞歸解法

摘要：題目描述輸入一棵二叉樹，求該樹的深度。遞歸解法非遞歸解法原來標(biāo)識(shí)當(dāng)前層是否遍歷完畢當(dāng)前彈出元素為時(shí)，說明一層以及遍歷完畢了，所以最后一層的彈出時(shí)不能再往隊(duì)列里面加了題目描述輸入一棵二叉樹，求該樹的深度。從根結(jié)點(diǎn)到葉結(jié)點(diǎn)依次經(jīng)過的結(jié)點(diǎn)（含根、葉結(jié)點(diǎn)）形成樹的一條路徑，最長(zhǎng)路徑的長(zhǎng)度為樹的深度。遞歸解法 function TreeNode(x) { this.val = x;...

Carl 2019-08-22 18:13 評(píng)論0 收藏0