【数据结构】【二叉树】二叉树的层序遍历解题报告

灰太狼 2023-02-28 01:27 75阅读 0赞

## 题目：二叉树的层序遍历 ##

## 解题思路【广度优先】 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAyNDQ2Mw_size_16_color_FFFFFF_t_70]

1.  根据先序/中序/后序的遍历经验我们知道非递归遍历一般都是入队，出对的操作
2.  .根据上图的遍历结果123456，应首先将1入队；然后再将2和3入队；怎么将2和3入队呢？那就先将1从队中弹出来，将1->left和1->right入队
3.  其次是3和4要入队，则我们需要将2从对中弹出来，然后2->left 2->right 将其入队；则这个时候看出来这个是一个先进先出的队列结构
4.  这个是思路很清楚了，代码就很简单了，首先将根节点入队；然后循环判断队列不为空为止；  
    从队列弹出节点，如果有左右孩子则入队

## 直接上代码 ##

type TreeNode struct {
        
    	     Val int
    	    Left *TreeNode
    	     Right *TreeNode
    	 }
    
    func levelOrder(root *TreeNode)[]int{
        
    	var result []int
    	tmpList :=list.New()
    	// 先将根节点放进去
    	tmpList.PushFront(root)
    	for tmpList.Len()!=0{
        
    		tmpDataInterface :=tmpList.Back()
    		tmpList.Remove(tmpDataInterface)
    		nodeData :=tmpDataInterface.Value.(*TreeNode)
    		// 出栈的顺序就是遍历的顺序，因此在出栈的时候将其放到数组中
    		result = append(result,nodeData.Val)
    		if nodeData.Left!=nil{
        
    			tmpList.PushFront(nodeData.Left)
    		}
    		if nodeData.Right!=nil{
        
    			tmpList.PushFront(nodeData.Right)
    		}
    	}
    	return result
    }

## 解题思路【深度优先】 ##

var result [][]int
    func levelOrder(root *TreeNode) [][]int {
        
    	result = make([][]int, 0)
    	_levelOrder(root, 0)
    	return result
    }
    // 注意：在先序/中序、遍历的时候这里将返回值放到参数参数中，传递的是一个指针，而在这里是一个二维不可以
    // 错误的示范： func _levelOrder(root *TreeNode, level int,result *[][]int) {  这个地方也没太能理解，还得加强理解
    func _levelOrder(root *TreeNode, level int) {
        
    	if root == nil {
        
    		return
    	}
    	// 这里有go语言的特性，怎么进行初始化，否则会index out of range ，这里非常重要，怎么进行判断对二维的数组在一维的时候进行初始化
    	// 在最开始的时候也没能想出来，在看到答案的时候结合递归的深度优先遍历来理解的
    	if level == len(result) {
        
    		result = append(result, []int{
        })
    	}
    	result[level] = append(result[level], root.Val)
    	if root.Left != nil {
        
    		_levelOrder(root.Left, level+1)
    	}
    	if root.Right != nil {
        
    		_levelOrder(root.Right, level+1)
    	}
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAyNDQ2Mw_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAyNDQ2Mw_size_16_color_FFFFFF_t_70]: /images/20230209/0bd748d9d5f8461e914a8e020d78d383.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODAyNDQ2Mw_size_16_color_FFFFFF_t_70_pic_center]: /images/20230209/9bc814714fcc4d7bb5ff1a2a7234a43a.png