Golang每日一练(leetDay0049) 二叉树专题（9）

原标题：Golang每日一练(leetDay0049) 二叉树专题（9）

144. 二叉树的前序遍历 Binary-tree Preorder Traversal ?

145. 二叉树的前序遍历 Binary-tree Postorder Traversal ?文章来源地址https://www.yii666.com/blog/405858.html

对比： 94. 二叉树的中序遍历 Binary-tree Inorder Traversal ?

146. LRU缓存 LRU Cache ??

? 每日一练刷题专栏 ?

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏

二叉树专题（9）第146题除外

144. 二叉树的前序遍历 Binary-tree Preorder Traversal

root

示例 1：

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

示例 2：

输入：root = []
输出：[]

示例 3：

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

示例 4：

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

示例 5：

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

提示：

[0, 100]-100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

公用的示例二叉树：

遍历结果：

前序遍历 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. 二叉树的后序遍历 Binary-tree Postorder Traversal

root

示例 1：

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

示例 2：

输入：root = []
输出：[]

示例 3：

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

提示：

[0, 100]-100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

代码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]

对比： 94. 二叉树的中序遍历 Binary-tree Inorder Traversal

root

示例 1：

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

示例 2：

输入：root = []
输出：[]

示例 3：

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

提示：

[0, 100]-100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

代码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]

三种遍历的递归对比

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

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)
}

三种遍历的迭代对比

注意左、右子节点的压栈顺序，以及后序结果中的“追加”实为“前插”

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

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。

LRUCache

LRUCache(int capacity)capacityint get(int key)key-1void put(int key, int value)keyvaluekey-valuecapacity

getputO(1)

示例：

输入
["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); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

1 <= capacity <= 30000 <= key <= 100000 <= value <= 10^52 * 10^5getput

代码：

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
    }
}

输出：

略

✨ 持续，努力奋斗做强刷题搬运工！

? 点赞，你的认可是我坚持的动力！

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

✎ 评论，你的意见是我进步的财富！

☸ 主页：https://hannyang.blog.csdn.net/

	Golang每日一练专栏
	Python每日一练专栏
	C/C++每日一练专栏
	Java每日一练专栏

Golang每日一练(leetDay0049) 二叉树专题（9）

144. 二叉树的前序遍历 Binary-tree Preorder Traversal

145. 二叉树的后序遍历 Binary-tree Postorder Traversal

对比： 94. 二叉树的中序遍历 Binary-tree Inorder Traversal

三种遍历的递归对比

三种遍历的迭代对比

146. LRU缓存 LRU Cache

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏