这是算法记录的第11天，主要是二叉树的前中后序遍历，分别使用了三种方法
对应leetcode题目为144.94.145
144.二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
思路
两种递归，一种迭代
递归的基于两种基本思路，一种是遍历一遍二叉树，是回溯思想；另一种是分解子问题，动态规划思想
迭代的话就是利用栈结构代替递归栈来保存中间处理的节点
代码
遍历-回溯
// 回溯
func preorderTraversal1(root *TreeNode) []int {
var res []int
var traverse func(node *TreeNode)
traverse = func(node *TreeNode) {
if node == nil {
return
}
res = append(res, node.Val)
traverse(node.Left)
traverse(node.Right)
}
traverse(root)
return res
}
分解-动态规划
// 动态规划
func preorderTraversal(root *TreeNode) []int {
var res []int
if root == nil {
return nil
}
res = append(res, root.Val)
//利用...将返回的切片打散
res = append(res, preorderTraversal(root.Left)...)
res = append(res, preorderTraversal(root.Right)...)
return res
}
迭代
实际上无需双向链表
import "container/list"
// 迭代：中左右
func preorderTraversal2(root *TreeNode) []int {
var ans []int
if root == nil {
return ans
}
// 内置的双向链表作为栈
st := list.New()
st.PushBack(root)
for st.Len() > 0 {
//中间节点的值保存下来
node := st.Remove(st.Back()).(*TreeNode) //断言
ans = append(ans, node.Val)
//按右左顺序进后面就是左右顺序出
if node.Right != nil {
st.PushBack(node.Right)
}
if node.Left != nil {
st.PushBack(node.Left)
}
}
return ans
}
上述代码使用双向链表作为栈的实现方式，主要是因为双向链表具有以下特点：
1、双向链表可以快速在链表末尾进行节点的插入和删除操作，这符合栈的后进先出（LIFO）的特点。
2、双向链表可以通过Back()方法获取链表尾部的节点，从而实现对栈顶元素的访问。
3、双向链表可以快速删除任意一个节点，这对于迭代遍历二叉树时需要跳过某些节点的情况特别有用。
因此，使用双向链表实现栈可以简化代码实现，并且提高算法的效率和灵活性。
但是我上面的代码只在后端进行了插入操作，完全没必要使用双端链表啊
You’re correct that the doubly linked list used in the code you provided is only used for pushing nodes to the back of the list and popping them from the back as well. So technically, a singly linked list would be sufficient for this implementation.
However, using a doubly linked list as a stack also has other advantages. For example, in certain situations where you need to remove an arbitrary node from the stack, a doubly linked list would allow you to do so in constant time, while a singly linked list would require traversing the list from the beginning to find the previous node, which would be O(n) time complexity.
Additionally, using a doubly linked list can make the code more readable and easier to understand, as it explicitly indicates that the list is being used as a stack, and it makes it easy to switch to other stack-based operations such as popping from the front if needed in the future.
So while a singly linked list could work in this specific implementation, using a doubly linked list as a stack is still a reasonable and valid choice.
94.二叉树的中序遍历
给你二叉树的根节点 root ，返回它节点值的 中序 遍历。
思路
对于递归的两种方法而言基本就是换个位置的区别
而迭代的话是需要先找到当前节点的最左端，路径中其他的节点先压入栈中，然后处理中间节点（出栈），再指向右节点，重复上面的过程，直到栈空且当前节点为空。
代码
递归
// 递归-动态规划
func inorderTraversal(root *TreeNode) []int {
var res []int
if root == nil {
return nil
}
//利用...将返回的切片打散
res = append(res, inorderTraversal(root.Left)...)
res = append(res, root.Val)
res = append(res, inorderTraversal(root.Right)...)
return res
}
// 递归-回溯
func inorderTraversal1(root *TreeNode) []int {
var res []int
var traverse func(node *TreeNode)
traverse = func(node *TreeNode) {
if node == nil {
return
}
traverse(node.Left)
//中序位置
res = append(res, node.Val)
traverse(node.Right)
}
traverse(root)
return res
}
迭代
// 迭代-利用栈结构
func inorderTraversal2(root *TreeNode) []int {
var ans []int
if root == nil {
return ans
}
//双向链表表示栈
st := list.New()
cur := root
//当前节点不为空或栈不为空
for cur != nil || st.Len() > 0 {
if cur != nil {
//压入栈中，然后继续访问左子树
st.PushBack(cur)
cur = cur.Left
} else {
//否则就将栈顶出栈，并作为遍历结果保存到ans中
cur = st.Remove(st.Back()).(*TreeNode)
//中序
ans = append(ans, cur.Val)
//继续遍历出栈节点的右子树
cur = cur.Right
}
}
return ans
}
145.二叉树的后序遍历
给你二叉树的根节点 root ，返回它节点值的 后序 遍历。
思路
这个就和前序遍历差不多了
代码
import "container/list"
// 动态规划
func postorderTraversal(root *TreeNode) []int {
var res []int
if root == nil {
return nil
}
//利用...将返回的切片打散
res = append(res, postorderTraversal(root.Left)...)
res = append(res, postorderTraversal(root.Right)...)
res = append(res, root.Val)
return res
}
// 回溯
func postorderTraversal1(root *TreeNode) []int {
var res []int
var traverse func(node *TreeNode)
traverse = func(node *TreeNode) {
if node == nil {
return
}
traverse(node.Left)
traverse(node.Right)
res = append(res, node.Val)
}
traverse(root)
return res
}
// 迭代：左右中
func postorderTraversal2(root *TreeNode) []int {
var ans []int
if root == nil {
return ans
}
// 内置的双向链表作为栈
st := list.New()
st.PushBack(root)
for st.Len() > 0 {
node := st.Remove(st.Back()).(*TreeNode)
if node.Left != nil {
st.PushBack(node.Left)
}
if node.Right != nil {
st.PushBack(node.Right)
}
//加到前面
ans = append([]int{node.Val}, ans...)
}
return ans
}
总结与区别
快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后序遍历
回溯与动态规划
回溯算法是一种基于深度优先搜索的算法，通常用于求解所有解或最优解的问题。 回溯算法会遍历所有可能的解，直到找到满足条件的解或者遍历完所有可能的情况。 回溯算法需要满足三个条件：路径、选择列表和结束条件。递归是实现回溯算法的一种方式， 因为回溯算法的过程可以看作是一种深度优先搜索的递归过程。
动态规划算法是一种自底向上的算法，通常用于求解最优化问题。 动态规划算法将问题划分成若干个子问题，递归地解决子问题，并将子问题的解合并成原问题的解。 动态规划算法需要满足两个条件：最优子结构和重叠子问题。递归也可以实现动态规划算法， 但是通常采用递推方式，因为递推的时间复杂度更低，而且可以避免递归调用的额外空间开销。