您好,登录后才能下订单哦!
今天就跟大家聊聊有关如何进行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 []int
for 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)/2
return &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.Left
r:=root.Right
if l==nil&& r==nil{
return root,root
}
if l==nil{
hr,tr:=flatten1(r)
root.Left=nil
root.Right=hr
return root,tr
}
if r==nil{
h,t:=flatten1(l)
root.Right=h
root.Left=nil
return root,t
}
h,t:=flatten1(l)
root.Right=h
root.Left=nil
hr,tr:=flatten1(r)
t.Right=hr
return root,tr
}
看完上述内容,你们对如何进行python二叉树链表相互转换有进一步的了解吗?如果还想了解更多知识或者相关内容,请关注亿速云行业资讯频道,感谢大家的支持。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。