算法篇：树之树的层次遍历

灰子学技术

发布于 2020-08-11 16:53:35

1.6K0

发布于 2020-08-11 16:53:35

文章被收录于专栏：灰子学技术灰子学技术

算法：

树的层次遍历是树的基本操作之一，包括二叉树的层次遍历，多叉树的层次遍历，以及二叉树层次遍历的变形题目，层次遍历+每一层的节点的翻转等操作。

对于这类题目，典型算法就是先将树按照层次存入数组当中，然后统一对每一层的数据进行数据处理。

题目1:

102. 二叉树的层序遍历

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

代码实现：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 /* 
 方法1:非递归操作
 */
 /*
func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }
    var stack []*TreeNode
    var result [][]int
    stack = append(stack,root)
    for {
        if len(stack) == 0 {
            break;
        }
        res,stack1 := helper(stack)
        if len(res) != 0 {
            result = append(result,res)
        }
        stack = stack1
    }
    return result
}
func helper(stack []*TreeNode)(res []int, stackRes []*TreeNode){
    if len(stack) == 0{
        return
    }
   
    for i:=0;i<len(stack); i++{
        node := stack[i]
        if node == nil {
            continue
        }
        res = append(res,node.Val)   
        stackRes = append(stackRes,node.Left)
        stackRes = append(stackRes,node.Right)
    }
    
    return
}
*/
/*
解法：队列来操作，
树的层次遍历，从左到右遍历树的每一层存入对应的数组即可
*/
/*
方法2:递归操作
利用二叉树的先序遍历方法，也就是先访问根节点，在访问做左孩子，然后访问右孩子。
*/
func levelOrder(root *TreeNode) [][]int {
    return preOrder(root, 0, [][]int{})
}

func preOrder(root *TreeNode, level int, res [][]int) [][]int  {
    if root == nil {
        return res
    }
    // 1.根节点的处理
    // 这里因为level从0开始计算的缘故，len放进去值之后就是1，所以==的时候，便是是新的一层开始
    if level == len(res) { 
        res = append(res,[]int{root.Val})
    } else {
        res[level] = append(res[level],root.Val)
    }
    // 2.左孩子节点的处理
    res = preOrder(root.Left,level+1,res)
    // 3.右孩子节点的处理
    res = preOrder(root.Right,level+1,res)
    return res
}

执行结果：

题目2:

https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/

代码实现：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func levelOrderBottom(root *TreeNode) [][]int {
    r := [][]int{}
    order(root,0,&r)
    for i,j:= 0, len(r)-1;i<j;{
        r[i],r[j] = r[j],r[i]
        i++
        j--
    }
    return r
}
func order(root *TreeNode,level int,res *[][]int)  {
    if root == nil {
        return
    }
    if len(*res)-1 < level {
        *res = append(*res,[]int{root.Val})
    } else {
        (*res)[level] = append((*res)[level],root.Val)
    }
    
    order(root.Left,level+1,res)
    order(root.Right,level+1,res)
    return 
}

执行结果：

题目3:

https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/

代码实现：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func zigzagLevelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }
    res := [][]int{}
    levelOrder(root,0, &res)
    for i:=0; i< len(res); i++ { 
        if i%2 == 1{
            j,k:=0,len(res[i])-1
            for j < k{
                res[i][j],res[i][k] = res[i][k],res[i][j] 
                j++
                k--
            }
        }
    }
    return res
}

func levelOrder(root *TreeNode, l int, res *[][]int) {
    if root == nil {
        return 
    }
    if len(*res)-1 < l  {
        *res = append(*res,[]int{root.Val})
    } else {
        (*res)[l] = append((*res)[l],root.Val)
    }
    levelOrder(root.Left,l+1,res)
    levelOrder(root.Right,l+1,res)
 
    return 
}
// 需要: 先按照层次去遍历存储，然后统一的做整理，调整需要转换的对应层次

结果输出：

题目4.

https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/

代码实现：

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func levelOrder(root *Node) [][]int {
    if root == nil {
        return nil
    }
    res := [][]int{}
    levelOrderOk(root,0,&res)
    return res
}

func levelOrderOk(root *Node,l int, res *[][]int){
    if len(*res)-1 < l {
        *res = append(*res,[]int{root.Val})
    } else {
        (*res)[l] = append((*res)[l],root.Val)
    }
    for _,t := range root.Children {
        levelOrderOk(t,l+1,res)
    }
    return 
}

执行结果：