golang刷leetcode 二叉树链表相互转换

golangLeetcode

发布于 2022-08-02 15:52:10

1590

发布于 2022-08-02 15:52:10

文章被收录于专栏：golang算法架构leetcode技术php

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，注意，左孩子和右孩子不一定是链表的前、后元素

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
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-03-14，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法