A,有序链表转换二叉搜索树
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
代码语言：javascript复制给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/
-3 9
/ /
-10 5解题思路：
1，平衡二叉树左右高度绝对值不超过1，所以链表中间元素是根元素
2，平衡二叉树左孩子<根<右孩子，所以左孩子是左半部分的根，右孩子是右半部分的根
3，对于树需要考虑边界情况：根空，左右同时空，左空／右空
4，链表找中间元素太麻烦，转化成数组
代码语言：javascript复制/**
* 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,二叉树展开为链表
给定一个二叉树，原地将它展开为链表。
例如，给定二叉树
代码语言：javascript复制 1
/
2 5
/
3 4 6将其展开为：
代码语言：javascript复制1
2
3
4
5
6解题思路：
1，前序遍历树，将树的左孩子转化为空，右孩子转化为后继节点
2，注意，左孩子和右孩子不一定是链表的前、后元素
3，将子树展开，然后串联起来：根->左子树头->左子树尾->右子树头->右子树尾
4，注意边界情况
代码语言：javascript复制/**
* 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
}
