【刷算法】一棵樹是否是另一棵樹的子結構

Chaz 發布于2019-08-26 12:09 / 2052人閱讀

題目描述

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

分析

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

代碼實現

/* 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);
}

GPU云服務器云服務器一棵樹用c語言打出一棵樹棵樹一棵

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

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

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

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

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

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

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

摘要：樹中結點的最大層次稱為樹的深度或高度。二叉樹有深度遍歷和廣度遍歷，深度遍歷有前序中序和后序三種遍歷方法。二叉樹的前序遍歷可以用來顯示目錄結構等中序遍歷可以實現表達式樹，在編譯器底層很有用后序遍歷可以用來實現計算目錄內的文件及其信息等。樹的簡介棧、隊列、鏈表等數據結構，都是順序數據結構。而樹是非順序數據結構。樹型結構是一類非常重要的非線性結構。直觀地，樹型結構是以分支關系定義的層次結...

Yuanf 2019-08-23 11:38 評論0 收藏0
【React進階系列】虛擬dom與diff算法

摘要：通過對樹進行層級控制，同一個父節點下的所有子節點。新老集合進行差異化對比，發現，則創建并插入至新集合，刪除老集合以此類推，創建并插入和，刪除和。虛擬dom Jsx 表面寫的是html，其實內部執行的是一段js createElement React.createElement( type, [props], [...children] ) createElement把這個...

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

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

Carl 2019-08-22 18:13 評論0 收藏0