今天跟大家聊聊如何将python二叉树链表相互转换。很多人可能不太了解。为了让大家更好的了解,边肖为大家总结了以下内容。希望你能从这篇文章中有所收获。
00-1010给定一个链表,其中的元素按升序排序,它被转换成一个高度平衡的二叉查找树。
在这个问题中,高度平衡的二叉树意味着二叉树的每个节点的左右子树的高度差的绝对值不超过1。
示例:
给定有序链表:[-10,-3,0,5,9],
一个可能的答案是:[0,-3,9,-10,null,5],它可以代表以下高度平衡的二叉查找树:
0
/\
-3 9
//
-10 5个解决问题的想法:
1.平衡二叉树左右高度的绝对值不超过1,所以链表的中间元素是根元素。
2.平衡二叉树的左子根和右子根,这样左子就是左半根,右子就是右半根。
3.对于树,考虑边界条件:根为空,左右同时为空,左右为空。
4.在链表中找中间元素太麻烦,所以转换成数组。
/** *单链表的定义。*键入列表节点结构{ * Val int * Next *列表节点* } *//** *二叉树节点的定义。*键入tree node struct { * Val int * Left * tree node * Right * tree node * } */func sorted listobst(head * list node)* tree node { var a[]int for c :=head;c!=零;c=c.Next{ a=append(a,c . Val)} return arrayToTree(a)} func arrayToTree(a[]int)* tree node { if len(a)1 { return nil } if len(a)==1 { return tree node { Val 3360 a[0]} } if len(a)==2 { return tree node { Val 3360 a[1],left : returne node { Val 3360 a[0]} } if len(a)==3 { return tree node { Val 333336 a }
sp; } 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二叉树链表相互转换有进一步的了解吗?如果还想了解更多知识或者相关内容,请关注行业资讯频道,感谢大家的支持。
内容来源网络,如有侵权,联系删除,本文地址:https://www.230890.com/zhan/144276.html