导航：首页 > 互联网科技 >

如何利用数组处理链表

发表于：2025-02-12 作者：千家信息网编辑

千家信息网最后更新 2025年02月12日，如何利用数组处理链表，相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。算法：这类题目的一个共同的特点是，转化成数组之后，可以有效的利用数组的

千家信息网最后更新 2025年02月12日如何利用数组处理链表

如何利用数组处理链表，相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。

算法：

这类题目的一个共同的特点是，转化成数组之后，可以有效的利用数组的有序性来更方便的解决问题。

核心思想是，先利用数据将树变成有序性，然后统一操作有序数组，进行构建；然后再通过数组进行统一操作就可以。

题目1:

代码实现：

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */func flatten(root *TreeNode)  {    // 1. 将树变成数组，利用数组的有序性    l := preOrder(root)    if l == nil {        return     }    // 2. 将有序数组统一构建成一个链式的树结构    for i:=1; i< len(l);i++ { // 这里要注意的是i 从1 开始，因为我们用到了i-1做前缀        pre,cur := l[i-1],l[i]        pre.Left = nil        pre.Right = cur    }    return }func preOrder(root *TreeNode) []*TreeNode {    if root == nil {        return nil    }    res := []*TreeNode{}    res = append(res,root)    l := preOrder(root.Left)    res = append(res,l...)    r := preOrder(root.Right)    res = append(res,r...)    return res}// 算法：// 核心思想是，先利用数据将树变成有序性，然后统一操作有序数组，进行构建

执行结果：

题目2:

这个题目可以通过数组的有序性来操作，表现虽然没有那么好，不过还是想把这个解法写了下来，用来表明数组的用途。

代码实现：

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */func convertBST(root *TreeNode) *TreeNode {    l := midOrder(root)    if l == nil {        return nil    }    sum := 0    for i:=len(l)-1;i>=0;i-- {        l[i].Val += sum        sum = l[i].Val    }    return root }
func midOrder(root *TreeNode) []*TreeNode {    if root == nil  {        return nil    }    res := []*TreeNode{}    l := midOrder(root.Left)    res = append(res,l...)    res = append(res,root)    r := midOrder(root.Right)    res = append(res,r...)    return res}