二叉樹的各種遍歷

中序遍歷:左節(jié)點(diǎn)(左子樹),中間節(jié)點(diǎn)奢米,右節(jié)點(diǎn)(右子樹)
前序遍歷:中間節(jié)點(diǎn)掏导,左節(jié)點(diǎn)(左子樹)享怀,右節(jié)點(diǎn)(右子樹)
后序遍歷:左節(jié)點(diǎn)(左子樹),右節(jié)點(diǎn)(右子樹)趟咆,中間節(jié)點(diǎn)
層序遍歷:從根節(jié)點(diǎn)到最底層節(jié)點(diǎn)添瓷,每一層遍歷


func Start() {

    root := &TreeNode{
        Val: 1,
        Left: &TreeNode{
            Val: 2,
            Left: &TreeNode{
                Val: 4,
            },
            Right: &TreeNode{
                Val: 5,
            },
        },
        Right: &TreeNode{
            Val: 3,
            Left: &TreeNode{
                Val: 6,
            },
            Right: &TreeNode{
                Val: 7,
            },
        },
    }

    fmt.Println(layer(root))
    fmt.Println(layerLoop(root))
}

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// 層序遍歷的迭代
func layerLoop(root *TreeNode) [][]int {
    var res [][]int

    stackData := list.New()
    index := 0

    if root != nil {
        stackData.PushBack(root)
    }

    // 當(dāng)隊(duì)列中數(shù)據(jù)為空的時(shí)候程序退出
    for stackData.Len() > 0 {

        // 新隊(duì)列
        stackData1 := list.New()
        var tmpRet []int
        // 遍歷當(dāng)前層數(shù)據(jù)
        for stackData.Len() > 0 {
            currentNode := stackData.Front()
            stackData.Remove(currentNode)
            current := currentNode.Value.(*TreeNode)

            // 當(dāng)前數(shù)據(jù)保存
            tmpRet = append(tmpRet, current.Val)

            // 左,右節(jié)點(diǎn)依次入隊(duì)列處理
            if current.Left != nil {
                stackData1.PushBack(current.Left)
            }

            if current.Right != nil {
                stackData1.PushBack(current.Right)
            }

        }

        res = append(res, tmpRet)
        // 交換新舊隊(duì)列位置
        stackData = stackData1

        // 層數(shù)加1
        index++

    }

    return res
}

// 層序遍歷的遞歸
func layer(root *TreeNode) [][]int {
    res := make([][]int, 0)
    var layerDeliver func(root *TreeNode, layer int)

    layerDeliver = func(root *TreeNode, layer int) {

        if root == nil {
            return
        }

        if len(res) == layer {
            res = append(res, make([]int, 0))
        }

        res[layer] = append(res[layer], root.Val)

        layer++
        layerDeliver(root.Left, layer)
        layerDeliver(root.Right, layer)
    }

    layerDeliver(root, 0)
    return res
}

/*
    后序遍歷:
        先從左到右 ,先葉子后節(jié)點(diǎn)的方式遍歷訪問左右子樹值纱,最后訪問根節(jié)點(diǎn)
*/
func after(root *TreeNode) []int {
    res := make([]int, 0)

    if root == nil {
        return res
    }

    left := after(root.Left)
    right := after(root.Right)

    return append(append(left, right...), root.Val)
}

func afterLoop(root *TreeNode) []int {
    var res []int
    var prev *TreeNode

    // 獲取棧處理
    stack := list.New()

    // 棧不為空或者根節(jié)點(diǎn)部位空的時(shí)候處理
    for root != nil || stack.Len() > 0 {

        // 一路往左走到底
        for root != nil {
            stack.PushBack(root)
            root = root.Left
        }

        // 取出一個(gè)數(shù)據(jù)處理
        tempNode := stack.Back()
        stack.Remove(tempNode)
        root = tempNode.Value.(*TreeNode)

        // 右節(jié)點(diǎn)沒有處理過或者已經(jīng)處理過右節(jié)點(diǎn)鳞贷,則處理當(dāng)前節(jié)點(diǎn)
        if root.Right == nil || root.Right == prev {
            res = append(res, root.Val)
            prev = root // 記錄下當(dāng)前處理節(jié)點(diǎn)
            root = nil  // 標(biāo)記該節(jié)點(diǎn)已經(jīng)處理完畢
        } else {
            // 右節(jié)點(diǎn)未處理過則需要入棧繼續(xù)處理
            stack.PushBack(root)
            root = root.Right
        }
    }

    return res
}

/*
    前序遍歷的定義:
        先訪問根節(jié)點(diǎn),然后前序遍歷左子樹虐唠,再前序遍歷右子樹

    遞歸方式
*/
func before(root *TreeNode) []int {
    res := make([]int, 0)
    var left, right []int

    if root == nil {
        return res
    }

    res = append(res, root.Val)

    left = before(root.Left)

    right = before(root.Right)

    return append(append([]int{root.Val}, left...), right...)
}

func beforeLoop(root *TreeNode) []int {
    res := make([]int, 0)

    stackData := list.New()

    for stackData.Len() > 0 || root != nil {

        if root != nil {
            res = append(res, root.Val)
            stackData.PushBack(root)
            root = root.Left
        } else {
            // 左子樹遍歷完畢再遍歷 右子樹
            node := stackData.Back()
            stackData.Remove(node)
            nodeData := node.Value.(*TreeNode)
            root = nodeData.Right
        }

    }

    return res
}

/*
    中序遍歷的定義:
    先遍歷根節(jié)點(diǎn)的左子樹搀愧,然后訪問根節(jié)點(diǎn)的,最后遍歷右子樹

    中序遍歷迭代
*/
func middleLoop(root *TreeNode) []int {

    res := make([]int, 0)

    if root == nil {
        return res
    }

    stackData := list.New()

    // 需要一個(gè)棧來處理
    for stackData.Len() > 0 || root != nil {

        if root != nil {
            stackData.PushBack(root)
            root = root.Left
        } else {
            tmp := stackData.Back()
            stackData.Remove(tmp)
            tmpNode := tmp.Value.(*TreeNode)

            res = append(res, tmpNode.Val)
            root = tmpNode.Right
        }
    }

    return res
}

/**
 *  中序遍歷 - 遞歸
 */
func middle(root *TreeNode) []int {

    var left, right []int

    if root == nil {
        return make([]int, 0)
    }

    // 處理左邊的數(shù)據(jù)
    left = middle(root.Left)

    right = middle(root.Right)

    res := append(append(left, root.Val), right...)
    return res
}

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末疆偿,一起剝皮案震驚了整個(gè)濱河市咱筛,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌杆故,老刑警劉巖迅箩,帶你破解...
    沈念sama閱讀 222,681評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異处铛,居然都是意外死亡饲趋,警方通過查閱死者的電腦和手機(jī)拐揭,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來奕塑,“玉大人堂污,你說我怎么就攤上這事×渑椋” “怎么了盟猖?”我有些...
    開封第一講書人閱讀 169,421評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長换棚。 經(jīng)常有香客問我扒披,道長,這世上最難降的妖魔是什么圃泡? 我笑而不...
    開封第一講書人閱讀 60,114評(píng)論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮愿险,結(jié)果婚禮上颇蜡,老公的妹妹穿的比我還像新娘。我一直安慰自己辆亏,他們只是感情好风秤,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評(píng)論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著扮叨,像睡著了一般缤弦。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上彻磁,一...
    開封第一講書人閱讀 52,713評(píng)論 1 312
  • 那天碍沐,我揣著相機(jī)與錄音,去河邊找鬼衷蜓。 笑死累提,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的磁浇。 我是一名探鬼主播斋陪,決...
    沈念sama閱讀 41,170評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢(mèng)啊……” “哼置吓!你這毒婦竟也來了无虚?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,116評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤衍锚,失蹤者是張志新(化名)和其女友劉穎友题,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體构拳,經(jīng)...
    沈念sama閱讀 46,651評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡咆爽,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評(píng)論 3 342
  • 正文 我和宋清朗相戀三年梁棠,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片斗埂。...
    茶點(diǎn)故事閱讀 40,865評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡符糊,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出呛凶,到底是詐尸還是另有隱情男娄,我是刑警寧澤,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布漾稀,位于F島的核電站模闲,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏崭捍。R本人自食惡果不足惜尸折,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評(píng)論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望殷蛇。 院中可真熱鬧实夹,春花似錦、人聲如沸粒梦。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽匀们。三九已至缴淋,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間泄朴,已是汗流浹背重抖。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評(píng)論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留叼旋,地道東北人仇哆。 一個(gè)月前我還...
    沈念sama閱讀 49,299評(píng)論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像夫植,于是被迫代替她去往敵國和親讹剔。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評(píng)論 2 361

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