特定深度节点链表

题面

给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。

示例：
输入：[1,2,3,4,5,null,7,8]

        1
       /  \ 
      2    3
     / \    \ 
    4   5    7
   /
  8

输出：[[1],[2,3],[4,5,7],[8]]

来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/list-of-d...

数据结构

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

type ListNode struct {
    Val  int
    Next *ListNode
}

分析

1. 深度递归计算树的层次
2. 循环队列每次记录上一层节点
3. 根据每层节点构建链表
4. 外层循环记数，与树的最大层比较，作为终止条件

数组建树

有序数组构建二叉树，用递归
分析 一维变二维，找出 父子索引关系 n,n*2+1,n*2+2

func createTree(arr []int, n int) *TreeNode {
    if n > len(arr)-1 {
        return nil
    }

    root := &TreeNode{Val: arr[n]}
    root.Left = createTree(arr, n*2+1)
    root.Right = createTree(arr, n*2+2)

    return root
}

深度计算

求二叉树深度，左右二选一，大者出众

func treeDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left := treeDepth(root.Left)
    right := treeDepth(root.Right)

    if left > right {
        return left + 1
    } else {
        return right + 1
    }
}

题解

func listOfDepth(tree *TreeNode) []*ListNode {
    // 计算最大深度
    maxDepth := treeDepth(tree)
    l := []*TreeNode{}
    node := []*ListNode{}
    // 记录循环层次
    sum := 0
    for {
        t := []*TreeNode{}
        for i := 0; i < len(l); i++ {
            if l[i].Left != nil {
                t = append(t, l[i].Left)
            }
            if l[i].Right != nil {
                t = append(t, l[i].Right)
            }
        }
        if len(l) < 1 {
            t = []*TreeNode{tree}
        }
        l = t
        sum++

        // 生成链表头
        head := &ListNode{Val: t[0].Val}
        prev := head
        for i := 1; i < len(t); i++ {
            prev.Next = &ListNode{Val: t[i].Val}
            prev = prev.Next
        }

        // 加入链表
        node = append(node, head)
        // 外层跳出,指定层次，以及大于树的最大深度
        if sum >= maxDepth {
            break
        }
    }
    return node
}

本作品采用《CC 协议》，转载必须注明作者和本文链接