特定深度节点链表

题面

给定一棵二叉树,设计一个算法,创建含有某一深度上所有节点的链表(比如,若一棵树的深度为 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 协议》,转载必须注明作者和本文链接
pardon110
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!
开发者 @ 社科大
文章
102
粉丝
12
喜欢
82
收藏
38
排名:102
访问:4.6 万
私信
所有博文