Shulou(Shulou.com)06/01 Report--

How to use arrays to deal with linked lists, I believe many inexperienced people are helpless about this, this article summarizes the causes and solutions of the problem, through this article I hope you can solve this problem.

Algorithm:

A common feature of this type of problem is that, after being converted into an array, the ordering of the array can be effectively used to solve the problem more conveniently.

The core idea is to first use the data to turn the tree into order, and then uniformly operate the ordered array to construct it; then uniformly operate through the array.

Topic 1:

Code implementation:

/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */func flatten(root *TreeNode) { // 1. Turn a tree into an array and take advantage of array orderliness. l := preOrder(root) if l == nil { return } // 2. The ordered array is unified into a chained tree structure 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}

Implementation results:

After reading the above, do you know how to use arrays to handle lists? If you still want to learn more skills or want to know more related content, welcome to pay attention to the industry information channel, thank you for reading!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.