Leetcode专题-103-二叉树的锯齿形层序遍历

ChatGPT 可用网址，仅供交流学习使用，如对您有所帮助，请收藏并推荐给需要的朋友。
https://ckai.xyz

leetcode链接：
https://leetcode.cn/problems/binary-tree-zigzag-level-order-t...
解题思路：
使用深度优先搜索（DFS）的方式遍历二叉树，并使用一个二维数组res来保存遍历结果。在遍历过程中，对于每个节点，首先判断它所在的层数是否已经在res中存在，如果不存在则新建一个空数组加入res中。然后根据节点所在的层数是否为偶数，将节点的值插入到res[depth]的末尾或开头。最后递归遍历节点的左右子树，同时将深度depth加1。最终返回res即为锯齿形层次遍历结果。

func zigzagLevelOrder(root *TreeNode) [][]int {
    res := [][]int{}

    var dfs func(*TreeNode, int)

    dfs = func(node *TreeNode, depth int){
        if node ==nil{
            return
        }
        if len(res)<=depth{
            res = append(res, []int{})
        }

        if depth&1==0{
            res[depth] = append(res[depth], node.Val)
        } else{
            res[depth] = append([]int{node.Val}, res[depth]...)
        }

        dfs(node.Left, depth+1)
        dfs(node.Right, depth+1)

    }

    dfs(root, 0)
    return res
}