「算法歸納」二叉樹

  • 一種分層數(shù)據(jù)的抽象模型
  • 前端工作中常見的樹包括:DOM樹砸民、級聯(lián)選擇器捉撮、樹形控件
  • JS中沒有樹蔓彩,但是可以用Object和Array構(gòu)建樹
  • 樹的常用操作:深度/廣度優(yōu)先遍歷恳守、先中后序遍歷

樹的深度與廣度優(yōu)先遍歷

  • 深度優(yōu)先遍歷:盡可能深的搜索樹的分支


    image.png
  • 廣度優(yōu)先遍歷:先訪問離根節(jié)點最近的節(jié)點


    image.png

深度優(yōu)先遍歷

  • 訪問根節(jié)點
  • 對根節(jié)點的children挨個進(jìn)行深度優(yōu)先遍歷
  • 遞歸
const tree = {
    val: 'a',
    children: [
        {
            val: 'b',
            children: [
                {
                    val: 'd',
                    children: []
                },
                {
                    val: 'e',
                    children: []
                }
            ]
        },
        {
            val: 'c',
            children: [
                {
                    val: 'f',
                    children: []
                }
            ]
        }
    ]
}

const dfs = (root) => {
    console.log(root)
    root.children.forEach(dfs)
}

dfs(tree)

廣度優(yōu)先遍歷

  • 新建一個隊列,把根節(jié)點入隊
  • 把隊頭出隊并訪問
  • 把隊頭的children挨個入隊
  • 重復(fù)第二步砌们、第三步直到隊列為空
const tree = {
    val: 'a',
    children: [
        {
            val: 'b',
            children: [
                {
                    val: 'd',
                    children: []
                },
                {
                    val: 'e',
                    children: []
                }
            ]
        },
        {
            val: 'c',
            children: [
                {
                    val: 'f',
                    children: []
                }
            ]
        }
    ]
}
const bfs = (root) => {
    const q = [root]
    while(q.length > 0) {
        const n = q.shift()
        console.log(n.val)
        n.children.forEach(child => {
            q.push(child)
        })
    }
}

bfs(tree)

二叉樹

  • 樹中每個節(jié)點最多只能有兩個子節(jié)點
  • 在JS中通常用Object來模擬二叉樹
const bt ={
    val: 1,
    left: {
        val: 2,
        left: {
            val: 4,
            left: null,
            right: null
        },
        right: {
            val: 5,
            left: null,
            right: null
        }
    },
    right: {
        val: 3,
        left: {
            val: 6,
            left: null,
            right: null
        },
        right: {
            val: 7,
            left: null,
            right: null
        }
    }
}

先序遍歷

  • 訪問根節(jié)點
  • 對根節(jié)點的左子樹進(jìn)行先序遍歷
  • 對根節(jié)點的右子樹進(jìn)行先序遍歷
image.png
const preorder = (root) => {
    if (!root) return
    console.log(root.val)
    preorder(root.left)
    preorder(root.right)
}
preorder(bt)

中序遍歷

  • 對根節(jié)點的左子樹進(jìn)行中序遍歷
  • 訪問根節(jié)點
  • 對根節(jié)點的右子樹進(jìn)行中序遍歷
image.png
const inorder = (root) => {
    if (!root) return
    inorder(root.left)
    console.log(root.val)
    inorder(root.right)
}

inorder(bt)

后序遍歷

  • 對根節(jié)點的左子樹進(jìn)行后序遍歷
  • 對根節(jié)點的右子樹進(jìn)行后序遍歷
  • 訪問根節(jié)點
image.png
const postorder = (root) => {
    if (!root) return
    postorder(root.left)
    postorder(root.right)
    console.log(root.val)
}

postorder(bt)

二叉樹的先中后序遍歷(非遞歸)

二叉樹先序遍歷

// 遞歸版
const preorder = root => {
    ...
    preorder(...)
    ...
}

如果在函數(shù)里面顷歌,調(diào)用另外一個函數(shù)蚜退,就會形成一個函數(shù)調(diào)用堆棧滩租,調(diào)用完畢后又被釋放

所以說颗圣,堆棧就是我們實現(xiàn)非遞歸版先中后序遍歷的關(guān)鍵,我們可以用堆棧來模擬遞歸操作

const preorder = root => {
    if (!root) return
    const stack = [root]
    while (stack.length) {
        const n = stack.pop()
        console.log(n)
        if (n.right) stack.push(n.right)
        if (n.left) stack.push(n.left)
    }
}

二叉樹中序遍歷

const inorder = root => {
    if (!root) return
    const stack = []
    let p = root
    
    while (stack.length || p) {
        while (p) {
            stack.push(p)
            p = p.left
        }
        const n = stack.pop()
        console.log(n.val)
        p = n.right
    }
}

二叉樹后序遍歷

const postorder = root => {
    if (!root) return
    const stack = [root]
    const outputStack = []
    while (stack.length) {
        const n = stack.pop()
        
        outputStack.push(n)
        if (n.left) stack.push(n.left)
        if (n.right) stack.push(n.right)
    }
    while (outputStack.length) {
        const n = outputStack.pop()
        console.log(n.val)
    }
}

二叉樹的最大深度

  • 求最大深度篮撑,考慮使用深度優(yōu)先遍歷
  • 在深度優(yōu)先遍歷過程中减细,記錄每個節(jié)點所在層級,找出最大層級
// 104.二叉樹的最大深度
var maxDepth = function(root) {
    let res = 0
    const dfs = (n, l) => {
        if (!n) return
        if (!n.left && !n.right) {
            // 葉子節(jié)點再計算最深層級
             res = Math.max(res, l)
        }
        dfs(n.left, l + 1)
        dfs(n.right, l + 1)
    }
    dfs(root, 1)
    return res
};

二叉樹的最小深度

思路:

  • 求最小深度赢笨,考慮使用廣度優(yōu)先遍歷
  • 在廣度優(yōu)先遍歷過程中未蝌,遇到葉子節(jié)點停止遍歷,返回節(jié)點層級

解題步驟:

  • 廣度優(yōu)先遍歷整棵樹茧妒,并記錄每個節(jié)點的層級
  • 遇到葉子節(jié)點萧吠,返回節(jié)點層級,停止遍歷
// 111.二叉樹的最小深度
var minDepth = function(root) {
    if (!root) {return 0}
    const q = [[root, 1]]
    while (q.length > 0) {

        const [n, l] = q.shift()
        if (!n.left && !n.right) return l
        if (n.left) q.push([n.left, l+1])
        if (n.right) q.push([n.right, l + 1])
    }

};

二叉樹的層序遍歷

  • 層序遍歷順序就是廣度優(yōu)先遍歷
  • 不過在遍歷時候需要記錄當(dāng)前節(jié)點所處的層級桐筏,方便將其添加到不同的數(shù)組中
// 102.二叉樹的層序遍歷
var levelOrder = function(root) {
    if (!root) return []
    const q = [root]
    const res = []

    while (q.length) {
        let len = q.length
        res.push([])
        while (len--) {
            const n = q.shift()
            res[res.length - 1].push(n.val)
            if (n.left) q.push(n.left)
            if (n.right) q.push(n.right)
        }
        
    }
    return res
};

二叉樹的中序遍歷

// 94.二叉樹的中序遍歷
// 遞歸
var inorderTraversal = function(root) {
    const res = []
    const rec = n => {
        if (!n) return
        rec(n.left)
        res.push(n.val)
        rec(n.right)
    }
    rec(root)
    return res
};
// 非遞歸
var inorderTraversal = function(root) {
    const res = []
    const stack = []
    let p = root
    while (stack.length || p) {
        while(p) {
            stack.push(p)
            p = p.left
        }
        const n = stack.pop()
        res.push(n.val)
        p = n.right
    }
    return res
};

路徑總和

  • 在深度優(yōu)先遍歷的過程中纸型,記錄當(dāng)前路徑的節(jié)點值的和
  • 在葉子節(jié)點處,判斷當(dāng)前路徑的節(jié)點值的和是否等于目標(biāo)值
// 112.路徑總和
var hasPathSum = function(root, targetSum) {
    if (!root) return false
    let result = false
    const dfs = (n, val) => {
        if (!n.left && !n.right && val === targetSum) result = true
        if (n.left) dfs(n.left, n.left.val + val)
        if (n.right) dfs(n.right, n.right.val + val)
    }
    dfs(root, root.val)
    return result
};

遍歷JSON的所有節(jié)點值

const json = {
    a: {
        b: {
            c: 1
        }
    },
    d: [1, 2]
}
dfs = (n, path) => {
    console.log(n)
    Object.keys(n).forEach(k => {
        dfs(n[k], path.concat(k))
    })
}
dfs(json, [])

總結(jié)

  • 樹是一種分層數(shù)據(jù)的抽象模型梅忌,在前端廣泛應(yīng)用
  • 樹的常用操作:深度/廣度優(yōu)先遍歷狰腌、先中后序遍歷...
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市牧氮,隨后出現(xiàn)的幾起案子琼腔,更是在濱河造成了極大的恐慌,老刑警劉巖踱葛,帶你破解...
    沈念sama閱讀 211,817評論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件丹莲,死亡現(xiàn)場離奇詭異光坝,居然都是意外死亡,警方通過查閱死者的電腦和手機甥材,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,329評論 3 385
  • 文/潘曉璐 我一進(jìn)店門教馆,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人擂达,你說我怎么就攤上這事〗鹤蹋” “怎么了板鬓?”我有些...
    開封第一講書人閱讀 157,354評論 0 348
  • 文/不壞的土叔 我叫張陵,是天一觀的道長究恤。 經(jīng)常有香客問我俭令,道長,這世上最難降的妖魔是什么部宿? 我笑而不...
    開封第一講書人閱讀 56,498評論 1 284
  • 正文 為了忘掉前任抄腔,我火速辦了婚禮,結(jié)果婚禮上理张,老公的妹妹穿的比我還像新娘赫蛇。我一直安慰自己,他們只是感情好雾叭,可當(dāng)我...
    茶點故事閱讀 65,600評論 6 386
  • 文/花漫 我一把揭開白布悟耘。 她就那樣靜靜地躺著,像睡著了一般织狐。 火紅的嫁衣襯著肌膚如雪暂幼。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 49,829評論 1 290
  • 那天移迫,我揣著相機與錄音旺嬉,去河邊找鬼。 笑死厨埋,一個胖子當(dāng)著我的面吹牛邪媳,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播荡陷,決...
    沈念sama閱讀 38,979評論 3 408
  • 文/蒼蘭香墨 我猛地睜開眼悲酷,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了亲善?” 一聲冷哼從身側(cè)響起设易,我...
    開封第一講書人閱讀 37,722評論 0 266
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎蛹头,沒想到半個月后顿肺,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體戏溺,經(jīng)...
    沈念sama閱讀 44,189評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,519評論 2 327
  • 正文 我和宋清朗相戀三年屠尊,在試婚紗的時候發(fā)現(xiàn)自己被綠了旷祸。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 38,654評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡讼昆,死狀恐怖托享,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情浸赫,我是刑警寧澤闰围,帶...
    沈念sama閱讀 34,329評論 4 330
  • 正文 年R本政府宣布,位于F島的核電站既峡,受9級特大地震影響羡榴,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜运敢,卻給世界環(huán)境...
    茶點故事閱讀 39,940評論 3 313
  • 文/蒙蒙 一校仑、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧传惠,春花似錦迄沫、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,762評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至愿汰,卻和暖如春困后,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背衬廷。 一陣腳步聲響...
    開封第一講書人閱讀 31,993評論 1 266
  • 我被黑心中介騙來泰國打工摇予, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人吗跋。 一個月前我還...
    沈念sama閱讀 46,382評論 2 360
  • 正文 我出身青樓侧戴,卻偏偏與公主長得像,于是被迫代替她去往敵國和親跌宛。 傳聞我的和親對象是個殘疾皇子酗宋,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 43,543評論 2 349

推薦閱讀更多精彩內(nèi)容