【刷算法】求二叉樹深度的遞歸以及非遞歸解法

Carl 發布于2019-08-22 18:13 / 1666人閱讀

摘要：題目描述輸入一棵二叉樹，求該樹的深度。遞歸解法非遞歸解法原來標識當前層是否遍歷完畢當前彈出元素為時，說明一層以及遍歷完畢了，所以最后一層的彈出時不能再往隊列里面加了

題目描述

輸入一棵二叉樹，求該樹的深度。從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的深度。

遞歸解法

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
function Depth(r) {
    if(r === null)
        return  0;
    return Math.max(Depth(r.left), Depth(r.right))+1;
}

非遞歸解法

function TreeDepth(r)
{
    if(r === null)
        return 0;
    var q = [];
    var depth = 0;
    q.push(r);
    // null原來標識當前層是否遍歷完畢
    q.push(null);
    
    while(q.length !== 0){
        var cur = q.shift();
        // 當前彈出元素為null時，說明一層以及遍歷完畢了，所以depth+1
        if(cur === null){
            depth++;
            if(q.length!==0)
                // 最后一層的null彈出時不能再往隊列里面加null了
                q.push(null);
        } 
        else{
            if(cur.left !== null)
                q.push(cur.left);
            if(cur.right !== null)
                q.push(cur.right);
        }
    }
    
    return depth;
}

云服務器 GPU云服務器非遞歸二叉樹遍歷最小二乘的遞歸算法非遞歸遍歷二叉樹算法

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

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

二叉樹那些事兒

摘要：大家在聊到二叉樹的時候，總會離不開鏈表。受限線性表主要包括棧和隊列，受限表示對結點的操作受限制。存儲結構線性表主要由順序表示或鏈式表示。鏈式表示指的是用一組任意的存儲單元存儲線性表中的數據元素，稱為線性表的鏈式存儲結構。大家在聊到二叉樹的時候，總會離不開鏈表。這里先帶大家一起了解一些基本概念。線性表概念線性表是最基本、最簡單、也是最常用的一種數據結構。線性表中數據元素之間的關...

Little_XM 2019-08-22 16:28 評論0 收藏0
我的面試準備過程--二叉樹(更新中)

摘要：寫在最前面導師貪腐出逃美國，兩年未歸，可憐了我。拿了小米和美團的，要被延期，失效，工作重新找。把準備過程紀錄下來，共勉。寫在最前面導師貪腐出逃美國，兩年未歸，可憐了我。拿了小米和美團的offer，要被延期，offer失效，工作重新找。把準備過程紀錄下來，共勉。二叉樹的基礎結點定義 public class TreeNode{ int val; TreeNode ...

Amio 2019-08-16 10:36 評論0 收藏0
【刷算法】翻轉二叉樹的遞歸和非遞歸解法

摘要：題目描述操作給定的二叉樹，將其變翻轉為源二叉樹的鏡像。輸入描述解題思路遞歸版本首先，對數據結構比較了解的話會想到用遞歸來解決。所謂遞歸，在計算機科學中是指一種通過重復將問題分解為同類的子問題而解決問題的方法來自維基百科。題目描述操作給定的二叉樹，將其變翻轉為源二叉樹的鏡像。輸入描述: 1 1 / ...

wangbjun 2019-08-22 18:06 評論0 收藏0
Javacript二叉樹常見算法實現及快速排序求第K大值

摘要：后面也寫了幾種常見的排序算法，并用快排求第大值，另外如果之前版的作者看到的話可以留言，我會標明文章引用。之前實習筆試的時候刷題一直用的java，也參考某篇文章寫過java版的二叉樹常見算法，因為馬上要轉正面試了，這幾天都在準備面試，就把之前的翻出來用javascript重新寫了一遍，二叉樹基本都是遞歸處理的，也比較簡單，就當做熱身。后面也寫了幾種常見的排序算法，并用快排求第K大值，另...

leeon 2019-08-26 12:15 評論0 收藏0