汕头个人建站模板,排版设计工作内容,网站建设三个友好,阿里云买域名算法day12
二叉树理论基础114 二叉树的前序遍历145 二叉树的后序遍历94 二叉树的中序遍历迭代法 二叉树理论基础
直接看代码随想录就完事了#xff0c;之前考研也学过#xff0c;大概都能理解 我这里就说说代码层面的。 二叉树的存储#xff1a; 1、链式存储#xff1a;这…算法day12
二叉树理论基础114 二叉树的前序遍历145 二叉树的后序遍历94 二叉树的中序遍历迭代法 二叉树理论基础
直接看代码随想录就完事了之前考研也学过大概都能理解 我这里就说说代码层面的。 二叉树的存储 1、链式存储这个就是我们平时用的左指针右指针那种写法的二叉树存储方式。 2、顺序存储这个就是利用数组来存二叉树值得一提的是结点与结点的孩子如何表示这个是通过下标直接来表示的如果父节点的数组下标是 i那么它的左孩子就是 i * 2 1右孩子就是 i * 2 2。
二叉树遍历 深度优先遍历 前序遍历递归法迭代法 中序遍历递归法迭代法 后序遍历递归法迭代法 广度优先遍历 层次遍历迭代法 一个技巧前中后这里指的是访问根节点的顺序。 前中后遍历的逻辑其实都可以借助栈使用递归的方式来实现。
二叉树的定义
type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode
}这简直和C一个样。 二叉树的递归遍历
下面的题目都是涉及二叉树的递归遍历。递归的流程我觉得是很简单的但是这个代码有时候容易搞混。所以这里对递归的写法做一个总结。
每次写递归都按照这三要素来写 1.确定递归函数的参数和返回值 确定哪些参数是递归的过程中需要处理的那么就在递归函数里加上这个参数 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型 2.确定终止条件 写完了递归算法, 运行的时候经常会遇到栈溢出的错误就是没写终止条件或者终止条件写的不对操作系统也是用一个栈的结构来保存每一层递归的信息如果递归没有终止操作系统的内存栈必然就会溢出。 3.确定单层递归的逻辑 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。 114二叉树的前序遍历
我知道逻辑就是先根后左右。c能写但是go写不出来看到go语言的代码我就傻掉了。 根本写不出 所以这里好好学学go语言怎么写的。 首先树结点的结构体这个必须要会写就和c的实现一样的。
func preorderTraversal(root *TreeNode) (res []int) {var traversal func(node *TreeNode)traversal func(node *TreeNode) {if node nil {return}res append(res,node.Val)traversal(node.Left)traversal(node.Right)}traversal(root)return res
}
代码逻辑 1.在这个函数中先定义一个递归函数traversal 注意这个函数是直接在内部定义的这个语法我说实话我还是学的太少了第一次见。这里把这个语法学了。 函数是可以在另一个函数的内部定义的定义的方式如下
traversal func(node *TreeNode) {if node nil {return}res append(res,node.Val)traversal(node.Left)traversal(node.Right)}我总结就是先声明然后进行实现这个语法格式了解之后多写写就有记忆了。
这个题我只能说已经结束了这其实就是利用了go语言的一个性质和leetcode题意要求由于leetcode要求返回的是结果切片所以这里我就要在这个函数里面调用一个函数从而直接返回我要的结果。所以说这个题也并非要按题解这么写。这个函数我可以放到外面定义的只是go语言有这个方便的性质。
这里我再写一个版本
func traversal(root *TreeNode,res *[]int){if root nil {return }*res append(*res,root.Val)traversal(root.Left,res)traversal(root.Right,res)
}func preorderTraversal(root *TreeNode) []int {res : []int{}traversal(root,res)return res
}这个我感觉更适合我理解的写法。 但是这个写法我自己写的时候也遇到问题 1.我第一次写的时候没有意思到res切片是引用类型所以我在函数调用的时候如果要对res产生影响那么我就必须要传指针所以在定义函数的时候我要传的是*[]int,然后传参的时候传的肯定是res。 2.还有一个同样的问题发生在append我在对res调用append的时候这个res必须是引用类型所以我就要加一个取值符号*对里面的参数一样如此。
总结注意引用类型。
自己写了这个版本之后我才知道题解这么用有啥好处题解这么写还用到了一个语法闭包
这里通过这个题再学学闭包 闭包是一种特殊的函数它可以捕获其创建时所在的作用域中的变量。在go语言中闭包是通过定义在另一个函数内部的匿名函数实现的。这些匿名函数能够访问并操作其外部函数的变量。
我相信看完这个闭包的定义肯定有很大的疑惑我这个代码里面不是有名字吗这里其实很多教程又省略了我又去查了资料。
这里我建议看我理解的这个 上面代码中严格来说我实现闭包的这个函数并不是匿名函数然而即使它被命名了它仍然可以访问并修改它的外部作用域(PreorferTraversal函数)中的变量res。它仍然符合闭包的行为特征。
所以这里就要进行更正 闭包的本质 闭包的核心特征是它能够捕获并使用其外部作用域中的变量。**在go语言中这通常是通过在一个函数内部定义另一个函数实现的。**这个内部函数可以是匿名的也可以是命名的。关键是前面加粗的这句话。
题解的做法完全就是利用了闭包的性质。 后面两个题很简单
145二叉树的后续遍历
func postorderTraversal(root *TreeNode) []int {res : []int{}var traversal func(root *TreeNode)traversal func(root *TreeNode){if root nil {return }traversal(root.Left)traversal(root.Right)res append(res,root.Val)}traversal(root)return res
}就是左右根 94 二叉树的中序遍历
左根右
func inorderTraversal(root *TreeNode) []int {res : []int{}var traversal func(root *TreeNode)traversal func(root *TreeNode){if root nil {return }traversal(root.Left)res append(res,root.Val)traversal(root.Right)}traversal(root)return res
}迭代法非递归实现遍历
思路非递归的实现其实就是用栈来模拟递归因为递归的实现就是每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中然后递归返回的时候从栈顶弹出上一次递归的各项参数所以这就是递归为什么可以返回上一层位置的原因。 所以非递归的代码实现就是用栈来实现。所以下面的代码我都会先开一个栈来辅助。
前序遍历
思路前序遍历是中左右每次先处理中间结点那么就先将根结点放入栈中然后将右孩子加入栈再加入左孩子有人可能觉得这里我搞返了。 为什么要先加入右孩子再加入左孩子因为这样出栈的时候才是中左右的顺序。 可以看看这个动画模拟实现的过程看看过程中遍历到不同结点时栈的变化 我对这个过程解读以下 一开始5先入栈5出栈5的右孩子6入栈然后左孩子4入栈。 此时栈的状态的结果 前序遍历输出5 栈中 6 4. 4出栈然后4的右孩子2入栈左孩子1入栈此时 前序遍历输出 5 4 栈中6 2 1 1 出栈由于1没有左右孩子那继续2出栈2也没有左右孩子然后6出栈6也没有左右孩子所以这个时候栈为空结束。
代码逻辑 1.既然要用到栈那就先把栈实现了这里要注意这栈的元素是什么是值还是树结点回答是树结点这里需要注意。在上面的图中可能显得稍微简化了一点但实际上是把树结点加入栈中。就像我们写递归写法一样我们进行递归下一层同样是对结点操作。 2.实现前序遍历的非递归解法 1.先创建一个刚刚实现的空栈再创建一个结果集装结果。 2.先将根结点root先入栈然后开始循环 3.for 循环是针对这个栈的只要栈不空就不会停止。 将栈顶元素出栈然后把这个栈顶元素的值加入结果集。然后先加入右结点再加入左结点
代码实现
type Stack []*TreeNodefunc (s *Stack) Push(node *TreeNode) {*s append(*s, node)
}func (s *Stack) Pop() *TreeNode {if s.IsEmpty() {return nil}index : len(*s) - 1element : (*s)[index]*s (*s)[:index]return element
}func (s *Stack) IsEmpty() bool {return len(*s) 0
}func preorderTraversal(root *TreeNode) []int {if root nil {return nil}stack : Stack{}stack.Push(root)result : []int{}for !stack.IsEmpty() {node : stack.Pop()result append(result, node.Val)if node.Right ! nil {stack.Push(node.Right)}if node.Left ! nil {stack.Push(node.Left)}}return result
}
中序遍历迭代法
注意有人可能想像递归写法一样我在前序遍历非递归的写法改以下就得到中序遍历迭代法。这是实现不了的因为不是一个逻辑。前序遍历的逻辑无法直接用到中序遍历上。 为什么中序写法和前序的写法不通用 因为前序的遍历顺序是根左右先访问的元素是中间结点而且要处理的元素也是中间结点所以才能写出相对简洁的代吗因为要访问的元素和要处理的元素顺序是一致的都是中间节点。 再看看中序中序是左根右先访问的是二叉树顶部的结点然后一层一层的往下层访问直到到达树的最左下然后才开始处理结点也就是访问结点这就造成了处理顺序和访问顺序是不一致的。
那么在使用迭代法写中序遍历就需要借用指针的遍历来帮助访问节点栈则用来处理节点上的元素。
思路 中序遍历的顺序是左中右 1.初始化栈和当前结点创建一个栈来存待访问的结点然后设置当前结点为根结点。
看懂这个就看懂了这个题的逻辑 什么是当前结点当前结点是正在处理的元素为什么需要当前结点在非递归的实现中需要一个指针或引用来追踪当前正在处理的结点这个指针就被称为当前结点。 当前结点如何用 遍历时不断地讲当前结点移动到其左子节点直到到达最左侧的结点。这个过程中沿途的结点都被推入栈中以备后续访问。 当到达最左侧结点且该结点没有左子结点时开始从栈中弹出结点每次从栈中弹出一个结点这个结点就称为新的”当前结点”然后处理这个结点并将当前结点移动到其右子结点。
2.遍历左子树当前节点非空时将其推入栈中并将当前节点设置为其左子节点。这个过程一直持续到最左端即没有左子节点为止。
3.访问节点和遍历右子树当前节点为空时表示到达最左端从栈中弹出一个元素这是当前最左侧的节点访问这个节点将节点值加入结果数组将“当前节点”设置为弹出节点的右子节点开始处理右子树
4.重复过程重复上述过程直到栈为空且当前节点也为空。这表示所有节点都已按中序遍历的顺序访问完毕。
核心 1.栈的使用 栈用来暂存还未访问的节点。由于栈的后进先出特性它能够保证在处理完左子树后能够回到相应的父节点再去处理右子树。
2.遍历到最左侧 一开始需要遍历到树的最左侧这是中序遍历开始访问节点的地方。
3.从栈中弹出节点 在没有左子节点可访问时从栈中弹出节点表示该节点的左子树已经处理完毕可以访问该节点了。
4.转向右子树 访问完节点后转向处理右子树即将当前节点设置为右子节点。
代码
func inorderTraversal(root *TreeNode) []int {var result []intstack : []*TreeNode{}currentNode : rootfor currentNode ! nil || len(stack) 0 {// 遍历到最左节点for currentNode ! nil {stack append(stack, currentNode)currentNode currentNode.Left}// 当前节点为空说明左边遍历到底了开始处理栈顶节点currentNode stack[len(stack)-1]stack stack[:len(stack)-1] // 弹出栈顶节点result append(result, currentNode.Val) // 添加到结果中// 转向右子树currentNode currentNode.Right}return result
}
后序遍历非递归实现
后序遍历只需要在前序遍历的基础是做调整就可以实现为什么 先序遍历是根左右后续遍历是左右根那么我们只需要调整一下先序遍历的代码顺序就变成中右左的遍历顺序然后在反转result数组输出的结果顺序就是左右中了。
可能这样看着还是有点不太懂。先看代码逻辑我来解读 func postorderTraversal(root *TreeNode) []int {if root nil {return nil}stack : []*TreeNode{root} // 创建一个栈并初始化为包含根节点result : []int{} // 结果数组用于存储遍历结果// 继续遍历直到栈为空for len(stack) 0 {node : stack[len(stack)-1] // 取出栈顶元素stack stack[:len(stack)-1] // 弹出栈顶元素// 将当前节点的值添加到结果数组的前面// 这样做是为了在最后反转遍历的顺序result append([]int{node.Val}, result...)// 如果存在左子节点将其推入栈中// 注意这里先处理左子节点因为我们希望它在右子节点之后被处理if node.Left ! nil {stack append(stack, node.Left)}// 如果存在右子节点将其推入栈中if node.Right ! nil {stack append(stack, node.Right)}}// 返回结果数组这个数组是“左-右-根”的顺序return result
}
1.栈还是和前序一样的用法用于存储待访问的解读首先将根节点压入栈中。 2.根-右-左的遍历顺序我们从栈中弹出一个节点首先访问这个节点根然后如果存在左子节点我们将其压入栈中接下来如果存在右子节点我们也将其压入栈中。由于栈是后进先出的这意味着右子节点将在左子节点之前被处理。 3.结果数组的构建每次从栈中弹出一个节点时我们将其值插入到结果数组的前端这样做实际上是在创建一个“根-右-左”的顺序的数组。但是因为我们总是在数组的前端插入新元素所以最终的数组实际上是“左-右-根”的顺序。
为什么这样做可以得到后序遍历的结果 在后序遍历中我们希望遵循“左-右-根”的顺序。由于我们是在结果数组的前端插入每个新访问的节点所以最后访问的节点根节点将出现在数组的最前面而第一个访问的节点最左侧的节点将出现在数组的最后面。这样即使我们的遍历顺序是“根-右-左”数组中元素的顺序却是“左-右-根”。
递归写法总结算法实现还是非常的好理解的 主要还是对go语言的语法学习。今天这个语法我也是头一次体会到了闭包的作用。当时学语法的时候由于没有使用场景所以学起来还是有很大差别的。
应用场景总结 在函数调用的时候对于一个引用类型如果你想通过函数调用对这个引用类型产生影响这个时候要么传指针要么用闭包。而且对于有些函数调用比如append我还需要对传递的指针通过取值符号*进行取值后才能调用这个函数。
递归写法和非递归写法哪个比较好好在哪里 递归写法 优点代码好写对于要解决的问题来说这种写法与问题直接的关系就显得很直观。 缺点递归可能会导致调用堆栈过深尤其是处理大规模数据的时候可能会出现堆栈溢出。而且每次递归调用都会增加额外的堆栈帧开销影响性能。
非递归写法 优点通常比递归写法有更好的性能表现而且无堆栈溢出风险。 缺点代码不好写代码的可读性下降设计比较困难。
总结递归好写性能差非递归难写性能好。
