如何利用数组处理链表
如何利用数组处理链表,相信很多没有经验的人对此束手无策,为此本文总结了问题出现的原因和解决方法,通过这篇文章希望你能解决这个问题。
为浦口等地区用户提供了全套网页设计制作服务,及浦口网站建设行业解决方案。主营业务为成都做网站、网站建设、浦口网站设计,以传统方式定制建设网站,并提供域名空间备案等一条龙服务,秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求,就会得到认可,从而选择与我们长期合作。这样,我们也可以走得更远!
算法:
这类题目的一个共同的特点是,转化成数组之后,可以有效的利用数组的有序性来更方便的解决问题。
核心思想是,先利用数据将树变成有序性,然后统一操作有序数组,进行构建;然后再通过数组进行统一操作就可以。
题目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
}
执行结果:
看完上述内容,你们掌握如何利用数组处理链表的方法了吗?如果还想学到更多技能或想了解更多相关内容,欢迎关注创新互联行业资讯频道,感谢各位的阅读!
新闻名称:如何利用数组处理链表
URL链接:http://scyanting.com/article/pidopd.html