您现在的位置是：首页 >技术交流 >Golang每日一练(leetDay0049) 二叉树专题（9）网站首页技术交流

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

Hann Yang 2023-06-28 12:00:04
简介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每日一练 专栏

二叉树专题（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 

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

公用的示例二叉树：

    3
   / 
  9  20
    /  
   15   7

遍历结果：

前序遍历 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) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(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 <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 10^5
  • 最多调用 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
    }
}

输出：

略

🌟 每日一练刷题专栏 🌟

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

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

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

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

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

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐