【代码随想录】算法训练计划14

算法训练计划14"/>

【代码随想录】算法训练计划14

1、递归——94. 中序遍历

题目：
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
输入：root = [1,null,2,3]
输出：[1,3,2]

思路：

• 看题意，要不要返回值
• 递归，前中后序递归，都一样，放的位置稍微变一下

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func inorderTraversal(root *TreeNode) []int {res := []int{}var traversal func(node *TreeNode) traversal = func(node *TreeNode) {if node == nil {return}traversal(node.Left)res = append(res, node.Val)traversal(node.Right)}traversal(root)return res
}

2、迭代（栈）——144. 前序遍历

题目：
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

思路：

• 用栈模拟，实现迭代
• 开始要判断 root==nil ，否则会出现空指针
• 前后迭代，区别就是反转顺序即可
• go有内置的栈,学习一下如何使用
• 中序迭代的栈模拟过程就不一样了，要再想一遍，画个流程图

 // 代码一刷，前序遍历——迭代法
func preorderTraversal(root *TreeNode) []int {res := []int{}if root == nil {return res}stack := list.New()stack.PushBack(root)for stack.Len() > 0 {node := stack.Remove(stack.Back()).(*TreeNode)res = append(res, node.Val)if node.Right != nil {stack.PushBack(node.Right)}if node.Left != nil {stack.PushBack(node.Left)}}return res
}// 迭代——代码一刷，后序遍历// go语言没有反转，自己实现一下下
func postorderTraversal(root *TreeNode) []int {res := []int{}if root == nil {return res}stack := list.New()stack.PushBack(root)for stack.Len() > 0 {node := stack.Remove(stack.Back()).(*TreeNode)res = append(res, node.Val)if node.Left != nil {stack.PushBack(node.Left)}if node.Right != nil {stack.PushBack(node.Right)}}return Reverse(res)
}
func Reverse(res []int) []int {n := len(res)for i:=0; i<n/2; i++ {res[i], res[n-i-1] = res[n-i-1], res[i]}return res
}// 迭代，栈模拟，代码一刷// 注意想明白，栈的模拟过程，不行就画个流程图
func inorderTraversal(root *TreeNode) []int {res := []int{}if root == nil {return res}stack := list.New()cur := rootfor cur != nil || stack.Len() > 0 {if cur != nil {stack.PushBack(cur)cur = cur.Left} else {cur = stack.Remove(stack.Back()).(*TreeNode)res = append(res, cur.Val)cur = cur.Right}}return res
}

3、统一迭代法

题目：
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

思路：

• 前序遍历——统一迭代法，很强
• 不要忘记 continue
• 记得 node 知道 .(*TreeNode)干嘛的
• 知道 e有.Value

func preorderTraversal(root *TreeNode) []int {res := []int{}if root == nil{return res}stack := list.New()stack.PushBack(root)var node *TreeNodefor stack.Len() > 0 {e := stack.Back()stack.Remove(e)if e.Value == nil {e = stack.Back()stack.Remove(e)node=e.Value.(*TreeNode)res = append(res, node.Val)continue}node = e.Value.(*TreeNode)// 前序，中左右，对应右左中if node.Right != nil {stack.PushBack(node.Right)}if node.Left != nil {stack.PushBack(node.Left)}stack.PushBack(node)stack.PushBack(nil)}return res
}

4、

题目：