扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
今天就跟大家聊聊有关如何进行python二叉树链表相互转换，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。
站在用户的角度思考问题，与客户深入沟通，找到郊区网站设计与郊区网站推广的解决方案，凭借多年的经验，让设计与互联网技术结合，创造个性化、用户体验好的作品，建站类型包括：网站设计制作、网站制作、企业官网、英文网站、手机端网站、网站推广、申请域名、网站空间、企业邮箱。业务覆盖郊区地区。
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5解题思路：
1，平衡二叉树左右高度绝对值不超过1，所以链表中间元素是根元素
2，平衡二叉树左孩子<根<右孩子，所以左孩子是左半部分的根，右孩子是右半部分的根
3，对于树需要考虑边界情况：根空，左右同时空，左空／右空
4，链表找中间元素太麻烦，转化成数组
/*** Definition for singly-linked list.* type ListNode struct {* Val int* Next *ListNode* }*//*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/func sortedListToBST(head *ListNode) *TreeNode {var a []intfor c:=head;c!=nil;c=c.Next{a=append(a,c.Val)}return arrayToTree(a)}func arrayToTree( a []int) *TreeNode {if len(a)<1{return nil}if len(a)==1{return &TreeNode{Val:a[0]}}if len(a)==2{return &TreeNode{Val:a[1],Left:&TreeNode{Val:a[0]}}}if len(a)==3{return &TreeNode{Val:a[1],Left:&TreeNode{Val:a[0]},Right:&TreeNode{Val:a[2]}}}m:=len(a)/2return &TreeNode{Val:a[m],Left:arrayToTree(a[:m]),Right:arrayToTree(a[m+1:])}}
B,二叉树展开为链表
给定一个二叉树，原地将它展开为链表。
例如，给定二叉树
1
/ \
2 5
/ \ \
3 4 6将其展开为：
1
\
2
\
3
\
4
\
5
\
6解题思路：
1，前序遍历树，将树的左孩子转化为空，右孩子转化为后继节点
2，注意，左孩子和右孩子不一定是链表的前、后元素
3，将子树展开，然后串联起来：根->左子树头->左子树尾->右子树头->右子树尾
4，注意边界情况
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/func flatten(root *TreeNode) {flatten1(root)}func flatten1(root *TreeNode) (head,tail *TreeNode) {if root==nil{return nil,nil}l:=root.Leftr:=root.Rightif l==nil&& r==nil{return root,root}if l==nil{hr,tr:=flatten1(r)root.Left=nilroot.Right=hrreturn root,tr}if r==nil{h,t:=flatten1(l)root.Right=hroot.Left=nilreturn root,t}h,t:=flatten1(l)root.Right=hroot.Left=nilhr,tr:=flatten1(r)t.Right=hrreturn root,tr}
看完上述内容，你们对如何进行python二叉树链表相互转换有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注创新互联行业资讯频道，感谢大家的支持。
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网