溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
今天就跟大家聊聊有關如何進行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二叉樹鏈表相互轉換有進一步的了解嗎？如果還想了解更多知識或者相關內容，請關注億速云行業資訊頻道，感謝大家的支持。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
