144. 二叉树的遍历「前序、中序、后序」 Golang实现
题目描述：给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
https://img2024.cnblogs.com/blog/2088072/202411/2088072-20241114201527345-548797112.png
思绪分析：
递归法：
前序遍历的顺序是中左右的顺序。那么每个子树都是这个顺序，所以可以使用递归进行遍历。递归遍历有3部曲
1.确定递归函数的参数和返回值。
因为返回值要求保存在一个数组中，所以递归函数的参数应该包括树的根节点和结果数组
` func preOrder(root *TreeNode,res *[]int) `
2.确定递归函数的终止条件
对于前序遍历来说，当某个根节点没有孩子节点的时候终止遍历。
```
if root==nil {
return
} ```
3.确定单层递归的逻辑
按照顺序进行遍历即可。
*res = append(*res, root.Val)
preOrder(root.Left,res)
preOrder(root.Right,res)最终的代码为：
点击检察代码func preorderTraversal(root *TreeNode) []int {
// 递归函数3步骤：
// 1.确定递归函数的参数2.确定递归函数的停止条件3.确定单层递归的调用逻辑
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 inorderTraversal(root *TreeNode) []int {
var res []int
if root==nil{
return res
}
getOrder(root,&res)
return res
}
func getOrder(root *TreeNode, res *[]int){
if root!=nil {
getOrder(root.Left,res)
*res = append(*res, root.Val)
getOrder(root.Right,res)
}
}后序遍历：
点击检察代码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)
}非递归版本
上方是三种遍历的递归方式，肯定要明确递归的3个步骤。但是递归一般复杂度高，很难解决数据量大的数据。在盘算机中递归就是用栈实现的，所以我们可以用栈来实现递归函数的非递归版本。但是三种遍历方式的写法会有区别。
三种遍历的非递归实在都是从根节点开始按照根左右的方式入栈，区别就在于什么时候应该出栈。
前序遍历
前序遍历的次序是根左右，由于是栈来实现，所有实际的入栈次序是根右左，当访问到根的时候将根节点入栈--记载其值，然后将根节点出栈，按照根节点的右左孩子的次序入栈，再根据栈顶元素作为根节点进行处理。函数结束条件则是栈的长度大于0.
点击检察代码func preorderTraversal(root *TreeNode) []int{
var res []int
if root==nil{
return res
}
var stack []*TreeNode
stack = append(stack, root)
for len(stack)>0 {
node:=stack
stack = stack[:len(stack)-1]
if node!=nil {
res = append(res, node.Val)
}
if node.Right != nil {
stack = append(stack, node.Right)
}
if node.Left!=nil {
stack = append(stack, node.Left)
}
}
return res
}中序遍历
中序的遍历次序是左中右。
入栈次序：从根节点开始，首先将当前节点的左子树一路压入栈中，直到当前节点没有左子树为止。
出栈条件：当栈顶节点没有左子树时，出栈该节点并访问它，然后继续对其右子树进行遍历。
函数结束条件是root!=nil || len(stack)>0 这是因为当遍历完左子树之后，回溯到整个树的root的时候，栈已经空了，但是右子树还没有入栈，所以还需要判断root是否为空。
点击检察代码func inorderTraversal(root *TreeNode) []int{
if root==nil {
return []int{}
}
res,stack:=[]int{},[]*TreeNode{}
for root!=nil || len(stack)>0 {
// 先遍历左子树
for root!=nil {
stack = append(stack, root)
root = root.Left
}
// 处理当前节点,最左下方的节点
root = stack
stack = stack[:len(stack)-1]
res = append(res, root.Val)
// 遍历右子树
root = root.Right
}
return res
}后序遍历
后序遍历的次序是：左-右-根。
入栈次序： 从根节点开始，首先将当前节点压入栈中，然后按照“左右”的次序将节点的左孩子和右孩子压入栈中。
出栈条件： 每次出栈栈顶元素后，仅在左右子树都已访问完成的情况下才访问根节点。为了包管这一点，通常需要借助一个额外的标记。所以我们通过pre指针来判断左右孩子是否已经访问过，只有他们都被访问过才能访问根节点。
因为入栈次序，所以栈顶元素必然是叶子节点，通过prev记载上一次访问的节点，如果当前节点是叶子节点，直接记载；若不是叶子节点，如果prev是当前节点的任一孩子，说明孩子节点访问完毕「2种情况，2个孩子和只有一个孩子，模拟一下便知」，则可以访问根节点了。
点击检察代码func postorderTraversal(root *TreeNode) []int{
if root==nil{
return []int{}
}
res,stack := []int{},[]*TreeNode{}
var prev *TreeNode
stack = append(stack, root)
for len(stack)>0{
current:=stack
if(current.Left== nil && current.Right ==nil) || (prev!=nil && (prev == current.Left || prev==current.Right)){
res = append(res, current.Val)
stack = stack[:len(stack)-1]
prev = current
}else{
if current.Right!=nil {
stack = append(stack, current.Right)
}
if current.Left != nil {
stack = append(stack, current.Left)
}
}
}
return res
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]