Golang每日一練(leetDay0049) 二叉樹(shù)專題（9）

這篇具有很好參考價(jià)值的文章主要介紹了Golang每日一練(leetDay0049) 二叉樹(shù)專題（9）。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

144. 二叉樹(shù)的前序遍歷 Binary-tree Preorder Traversal????

145. 二叉樹(shù)的前序遍歷 Binary-tree Postorder Traversal????

對(duì)比： 94. 二叉樹(shù)的中序遍歷 Binary-tree Inorder Traversal????

146. LRU緩存 LRU Cache??????

?? 每日一練刷題專欄???

Golang每日一練專欄

Python每日一練專欄

C/C++每日一練專欄

Java每日一練專欄

二叉樹(shù)專題（9）第146題除外

144. 二叉樹(shù)的前序遍歷 Binary-tree Preorder Traversal

給你二叉樹(shù)的根節(jié)點(diǎn)?root?，返回它節(jié)點(diǎn)值的?前序?遍歷。

示例 1：

Golang每日一練(leetDay0049) 二叉樹(shù)專題（9）

輸入：root = [1,null,2,3]
輸出：[1,2,3]

示例 2：

輸入：root = []
輸出：[]

示例 3：

輸入：root = [1]
輸出：[1]

示例 4：

Golang每日一練(leetDay0049) 二叉樹(shù)專題（9）

輸入：root = [1,2]
輸出：[1,2]

示例 5：

Golang每日一練(leetDay0049) 二叉樹(shù)專題（9）

輸入：root = [1,null,2]
輸出：[1,2]

提示：

樹(shù)中節(jié)點(diǎn)數(shù)目在范圍?[0, 100]?內(nèi)
-100 <= Node.val <= 100?

進(jìn)階：遞歸算法很簡(jiǎn)單，你可以通過(guò)迭代算法完成嗎？

公用的示例二叉樹(shù)：

遍歷結(jié)果：

前序遍歷 preorder  = [3,9,20,15,7]
中序遍歷 inorder   =?[9,3,15,20,7]
后序遍歷 postorder = [9,15,7,20,3]

?代碼1： 遞歸

package main

import (
	"fmt"
)

const null = -1 << 31

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

func preorderTraversal(root *TreeNode) []int {
	var res []int
	preorder(root, &res)
	return res
}

func preorder(root *TreeNode, res *[]int) {
	if root == nil {
		return
	}
	*res = append(*res, root.Val)
	preorder(root.Left, res)
	preorder(root.Right, res)
}

func buildTree(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}
	root := &TreeNode{Val: nums[0]}
	Queue := []*TreeNode{root}
	idx := 1
	for idx < len(nums) {
		node := Queue[0]
		Queue = Queue[1:]
		if nums[idx] != null {
			node.Left = &TreeNode{Val: nums[idx]}
			Queue = append(Queue, node.Left)
		}
		idx++
		if idx < len(nums) && nums[idx] != null {
			node.Right = &TreeNode{Val: nums[idx]}
			Queue = append(Queue, node.Right)
		}
		idx++
	}
	return root
}

func ArrayToString(arr []int) string {
	res := "["
	for i := 0; i < len(arr); i++ {
		res += fmt.Sprint(arr[i])
		if i != len(arr)-1 {
			res += ","
		}
	}
	return res + "]"
}

func main() {
	nums := []int{1, null, 2, 3}
	root := buildTree(nums)
	fmt.Println(ArrayToString(preorderTraversal(root)))
	nums = []int{3, 9, 20, null, null, 15, 7}
	root = buildTree(nums)
	fmt.Println(ArrayToString(preorderTraversal(root)))
}

?代碼2：?迭代

package main

import (
	"fmt"
)

const null = -1 << 31

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

func preorderTraversal(root *TreeNode) []int {
	var res []int
	if root == nil {
		return res
	}
	stack := []*TreeNode{}
	stack = append(stack, root)
	for len(stack) > 0 {
		cur := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res = append(res, cur.Val)
		if cur.Right != nil {
			stack = append(stack, cur.Right)
		}
		if cur.Left != nil {
			stack = append(stack, cur.Left)
		}
	}
	return res
}

func buildTree(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}
	root := &TreeNode{Val: nums[0]}
	Queue := []*TreeNode{root}
	idx := 1
	for idx < len(nums) {
		node := Queue[0]
		Queue = Queue[1:]
		if nums[idx] != null {
			node.Left = &TreeNode{Val: nums[idx]}
			Queue = append(Queue, node.Left)
		}
		idx++
		if idx < len(nums) && nums[idx] != null {
			node.Right = &TreeNode{Val: nums[idx]}
			Queue = append(Queue, node.Right)
		}
		idx++
	}
	return root
}

func ArrayToString(arr []int) string {
	res := "["
	for i := 0; i < len(arr); i++ {
		res += fmt.Sprint(arr[i])
		if i != len(arr)-1 {
			res += ","
		}
	}
	return res + "]"
}

func main() {
	nums := []int{1, null, 2, 3}
	root := buildTree(nums)
	fmt.Println(ArrayToString(preorderTraversal(root)))
	nums = []int{3, 9, 20, null, null, 15, 7}
	root = buildTree(nums)
	fmt.Println(ArrayToString(preorderTraversal(root)))
}

輸出：

[1,2,3]
[3,9,20,15,7]

145. 二叉樹(shù)的后序遍歷 Binary-tree Postorder Traversal

給你一棵二叉樹(shù)的根節(jié)點(diǎn)?root?，返回其節(jié)點(diǎn)值的?后序遍歷?。

示例 1：

Golang每日一練(leetDay0049) 二叉樹(shù)專題（9）

輸入：root = [1,null,2,3]
輸出：[3,2,1]

示例 2：

輸入：root = []
輸出：[]

示例 3：

輸入：root = [1]
輸出：[1]

提示：

樹(shù)中節(jié)點(diǎn)的數(shù)目在范圍?[0, 100]?內(nèi)
-100 <= Node.val <= 100

進(jìn)階：遞歸算法很簡(jiǎn)單，你可以通過(guò)迭代算法完成嗎？

?代碼1： 遞歸

package main

import (
	"fmt"
)

const null = -1 << 31

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

func postorderTraversal(root *TreeNode) []int {
	var res []int
	postorder(root, &res)
	return res
}

func postorder(root *TreeNode, res *[]int) {
	if root == nil {
		return
	}
	postorder(root.Left, res)
	postorder(root.Right, res)
	*res = append(*res, root.Val)
}

func buildTree(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}
	root := &TreeNode{Val: nums[0]}
	Queue := []*TreeNode{root}
	idx := 1
	for idx < len(nums) {
		node := Queue[0]
		Queue = Queue[1:]
		if nums[idx] != null {
			node.Left = &TreeNode{Val: nums[idx]}
			Queue = append(Queue, node.Left)
		}
		idx++
		if idx < len(nums) && nums[idx] != null {
			node.Right = &TreeNode{Val: nums[idx]}
			Queue = append(Queue, node.Right)
		}
		idx++
	}
	return root
}

func ArrayToString(arr []int) string {
	res := "["
	for i := 0; i < len(arr); i++ {
		res += fmt.Sprint(arr[i])
		if i != len(arr)-1 {
			res += ","
		}
	}
	return res + "]"
}

func main() {
	nums := []int{1, null, 2, 3}
	root := buildTree(nums)
	fmt.Println(ArrayToString(postorderTraversal(root)))
	nums = []int{3, 9, 20, null, null, 15, 7}
	root = buildTree(nums)
	fmt.Println(ArrayToString(postorderTraversal(root)))
}

?代碼2：?迭代

package main

import (
	"fmt"
)

const null = -1 << 31

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

func postorderTraversal(root *TreeNode) []int {
	var res []int
	if root == nil {
		return res
	}
	stack := []*TreeNode{}
	stack = append(stack, root)
	for len(stack) > 0 {
		cur := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res = append([]int{cur.Val}, res...)
		if cur.Left != nil {
			stack = append(stack, cur.Left)
		}
		if cur.Right != nil {
			stack = append(stack, cur.Right)
		}
	}
	return res
}

func buildTree(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}
	root := &TreeNode{Val: nums[0]}
	Queue := []*TreeNode{root}
	idx := 1
	for idx < len(nums) {
		node := Queue[0]
		Queue = Queue[1:]
		if nums[idx] != null {
			node.Left = &TreeNode{Val: nums[idx]}
			Queue = append(Queue, node.Left)
		}
		idx++
		if idx < len(nums) && nums[idx] != null {
			node.Right = &TreeNode{Val: nums[idx]}
			Queue = append(Queue, node.Right)
		}
		idx++
	}
	return root
}

func ArrayToString(arr []int) string {
	res := "["
	for i := 0; i < len(arr); i++ {
		res += fmt.Sprint(arr[i])
		if i != len(arr)-1 {
			res += ","
		}
	}
	return res + "]"
}

func main() {
	nums := []int{1, null, 2, 3}
	root := buildTree(nums)
	fmt.Println(ArrayToString(postorderTraversal(root)))
	nums = []int{3, 9, 20, null, null, 15, 7}
	root = buildTree(nums)
	fmt.Println(ArrayToString(postorderTraversal(root)))
}

輸出：

[3,2,1]
[9,15,7,20,3]

對(duì)比： 94. 二叉樹(shù)的中序遍歷 Binary-tree Inorder Traversal

給定一個(gè)二叉樹(shù)的根節(jié)點(diǎn)?root?，返回?它的?中序?遍歷?。

示例 1：

Golang每日一練(leetDay0049) 二叉樹(shù)專題（9）

輸入：root = [1,null,2,3]
輸出：[1,3,2]

示例 2：

輸入：root = []
輸出：[]

示例 3：

輸入：root = [1]
輸出：[1]

提示：

樹(shù)中節(jié)點(diǎn)數(shù)目在范圍?[0, 100]?內(nèi)
-100 <= Node.val <= 100

進(jìn)階:?遞歸算法很簡(jiǎn)單，你可以通過(guò)迭代算法完成嗎？

代碼1：遞歸法

package main

import (
	"fmt"
)

const null = -1 << 31

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

func inorderTraversal(root *TreeNode) []int {
	var res []int
	inorder(root, &res)
	return res
}

func inorder(root *TreeNode, res *[]int) {
	if root == nil {
		return
	}
	inorder(root.Left, res)
	*res = append(*res, root.Val)
	inorder(root.Right, res)
}

func buildTree(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}
	root := &TreeNode{Val: nums[0]}
	Queue := []*TreeNode{root}
	idx := 1
	for idx < len(nums) {
		node := Queue[0]
		Queue = Queue[1:]
		if nums[idx] != null {
			node.Left = &TreeNode{Val: nums[idx]}
			Queue = append(Queue, node.Left)
		}
		idx++
		if idx < len(nums) && nums[idx] != null {
			node.Right = &TreeNode{Val: nums[idx]}
			Queue = append(Queue, node.Right)
		}
		idx++
	}
	return root
}

func ArrayToString(arr []int) string {
	res := "["
	for i := 0; i < len(arr); i++ {
		res += fmt.Sprint(arr[i])
		if i != len(arr)-1 {
			res += ","
		}
	}
	return res + "]"
}

func main() {
	nums := []int{1, null, 2, 3}
	root := buildTree(nums)
	fmt.Println(ArrayToString(inorderTraversal(root)))
	nums = []int{3, 9, 20, null, null, 15, 7}
	root = buildTree(nums)
	fmt.Println(ArrayToString(inorderTraversal(root)))
}

代碼2：迭代法

package main

import (
	"fmt"
)

const null = -1 << 31

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

func inorderTraversal(root *TreeNode) []int {
	var res []int
	stack := []*TreeNode{}
	cur := root
	for cur != nil || len(stack) > 0 {
		for cur != nil {
			stack = append(stack, cur)
			cur = cur.Left
		}
		cur = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res = append(res, cur.Val)
		cur = cur.Right
	}
	return res
}

func buildTree(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}
	root := &TreeNode{Val: nums[0]}
	Queue := []*TreeNode{root}
	idx := 1
	for idx < len(nums) {
		node := Queue[0]
		Queue = Queue[1:]
		if nums[idx] != null {
			node.Left = &TreeNode{Val: nums[idx]}
			Queue = append(Queue, node.Left)
		}
		idx++
		if idx < len(nums) && nums[idx] != null {
			node.Right = &TreeNode{Val: nums[idx]}
			Queue = append(Queue, node.Right)
		}
		idx++
	}
	return root
}

func ArrayToString(arr []int) string {
	res := "["
	for i := 0; i < len(arr); i++ {
		res += fmt.Sprint(arr[i])
		if i != len(arr)-1 {
			res += ","
		}
	}
	return res + "]"
}

func main() {
	nums := []int{1, null, 2, 3}
	root := buildTree(nums)
	fmt.Println(ArrayToString(inorderTraversal(root)))
	nums = []int{3, 9, 20, null, null, 15, 7}
	root = buildTree(nums)
	fmt.Println(ArrayToString(inorderTraversal(root)))
}

輸出：

[1,3,2]
[9,3,15,20,7]

三種遍歷的遞歸對(duì)比

“根左右、左根右、左右根”

func preorder(root *TreeNode, res *[]int) {
	*res = append(*res, root.Val)
	preorder(root.Left, res)
	preorder(root.Right, res)
}

func inorder(root *TreeNode, res *[]int) {
	inorder(root.Left, res)
	*res = append(*res, root.Val)
	inorder(root.Right, res)
}

func postorder(root *TreeNode, res *[]int) {
	postorder(root.Left, res)
	postorder(root.Right, res)
	*res = append(*res, root.Val)
}

三種遍歷的迭代對(duì)比

注意左、右子節(jié)點(diǎn)的壓棧順序，以及后序結(jié)果中的“追加”實(shí)為“前插”

func preorderTraversal(root *TreeNode) []int {
    var res []int
    if root == nil {
        return res
    }
    stack := []*TreeNode{}
    stack = append(stack, root)
    for len(stack) > 0 {
        cur := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, cur.Val)
        if cur.Right != nil {
            stack = append(stack, cur.Right)
        }
        if cur.Left != nil {
            stack = append(stack, cur.Left)
        }
    }
    return res
}

func inorderTraversal(root *TreeNode) []int {
    var res []int
    stack := []*TreeNode{}
    cur := root
    for cur != nil || len(stack) > 0 {
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }
        cur = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, cur.Val)
        cur = cur.Right
    }
    return res
}

func postorderTraversal(root *Treecur) []int {
    var res []int
    if root == nil {
        return res
    }
    stack := []*Treecur{}
    stack = append(stack, root)
    for len(stack) > 0 {
        cur := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append([]int{cur.Val}, res...)
        if cur.Left != nil {
            stack = append(stack, cur.Left)
        }
        if cur.Right != nil {
            stack = append(stack, cur.Right)
        }
    }
    return res
}

146. LRU緩存 LRU Cache

請(qǐng)你設(shè)計(jì)并實(shí)現(xiàn)一個(gè)滿足? LRU (最近最少使用) 緩存 ?約束的數(shù)據(jù)結(jié)構(gòu)。

實(shí)現(xiàn)?LRUCache?類：

LRUCache(int capacity)?以?正整數(shù)?作為容量?capacity?初始化 LRU 緩存
int get(int key)?如果關(guān)鍵字?key?存在于緩存中，則返回關(guān)鍵字的值，否則返回?-1?。
void put(int key, int value)?如果關(guān)鍵字?key?已經(jīng)存在，則變更其數(shù)據(jù)值?value?；如果不存在，則向緩存中插入該組?key-value?。如果插入操作導(dǎo)致關(guān)鍵字?jǐn)?shù)量超過(guò)?capacity?，則應(yīng)該?逐出?最久未使用的關(guān)鍵字。

函數(shù)?get?和?put?必須以?O(1)?的平均時(shí)間復(fù)雜度運(yùn)行。

示例：

輸入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
輸出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解釋
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 緩存是 {1=1}
lRUCache.put(2, 2); // 緩存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 該操作會(huì)使得關(guān)鍵字 2 作廢，緩存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 該操作會(huì)使得關(guān)鍵字 1 作廢，緩存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 10^5
最多調(diào)用?2 * 10^5?次?get?和?put

?代碼：

type LRUCache struct {
    capacity int
    cache    map[int]*list.Element
    list     *list.List
}

type pair struct {
    key   int
    value int
}

func Constructor(capacity int) LRUCache {
    return LRUCache{
        capacity: capacity,
        cache:    make(map[int]*list.Element),
        list:     list.New(),
    }
}

func (c *LRUCache) Get(key int) int {
    if elem, ok := c.cache[key]; ok {
        c.list.MoveToFront(elem)
        return elem.Value.(*pair).value
    }
    return -1
}

func (c *LRUCache) Put(key int, value int) {
    if elem, ok := c.cache[key]; ok {
        elem.Value.(*pair).value = value
        c.list.MoveToFront(elem)
    } else {
        if c.list.Len() == c.capacity {
            // remove the least recently used element
            tailElem := c.list.Back()
            delete(c.cache, tailElem.Value.(*pair).key)
            c.list.Remove(tailElem)
        }
        // insert new element to front
        newElem := c.list.PushFront(&pair{key, value})
        c.cache[key] = newElem
    }
}

輸出：

略

?? 每日一練刷題專欄???

? 持續(xù)，努力奮斗做強(qiáng)刷題搬運(yùn)工！

?? 點(diǎn)贊，你的認(rèn)可是我堅(jiān)持的動(dòng)力！?

???收藏，你的青睞是我努力的方向！?

? 評(píng)論，你的意見(jiàn)是我進(jìn)步的財(cái)富！??

??主頁(yè)：https://hannyang.blog.csdn.net/?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-440476.html

	Golang每日一練專欄
	Python每日一練專欄
	C/C++每日一練專欄
	Java每日一練專欄

到了這里，關(guān)于Golang每日一練(leetDay0049) 二叉樹(shù)專題（9）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！