如何进行python二叉树链表相互转换

发布时间:2021-12-13 16:36:32 作者:柒染
来源:亿速云 阅读:185

今天就跟大家聊聊有关如何进行python二叉树链表相互转换,可能很多人都不太了解,为了让大家更加了解,小编给大家总结了以下内容,希望大家根据这篇文章可以有所收获。

A,有序链表转换二叉搜索树

给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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二叉树链表相互转换有进一步的了解吗?如果还想了解更多知识或者相关内容,请关注亿速云行业资讯频道,感谢大家的支持。

推荐阅读:
  1. python链表
  2. 怎么在python中对链表进行反转

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

python 二叉树

上一篇:如何从前序与中序遍历序列构造python二叉树

下一篇:Docker镜像安全性举例分析

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》