func ReverseList( pHead *ListNode ) *ListNode {
    if pHead==nil||pHead.Next==nil{
        return pHead
    }
    p:=&ListNode{Val:-1,Next:pHead} //设置一个头节点，防止冲突
    pHead=p
    p=pHead.Next
    q:=p
    for p.Next!=nil{
        q=p.Next
        p.Next=q.Next
        q.Next=pHead.Next     //这道题的重点在这里=头节点的下一个
        pHead.Next=q
    }
    return pHead.Next
}

func reverseBetween( head *ListNode ,  m int ,  n int ) *ListNode {
    // write code here
    if head.Next==nil||m==n||head==nil{ //m=n相当于没有翻转
      return head
    }
    p:=&ListNode{Val:-1,Next:head}
    head=p
    for i:=1;i<m;i++{  // 这里的m,n不是链表里面的值 是第几个数  傻逼
      p=p.Next
    }
    q:=p.Next
    cur:=q
    for i:=0;i<n-m;i++{
      cur=q.Next
      q.Next=cur.Next
      cur.Next=p.Next
      p.Next=cur   
    }
    return head.Next
}

func reverseBetween(head *ListNode, left, right int) *ListNode {
  pre:=&ListNode{-1,head}//设置头结点，防止left为1干扰
  head=pre
  for i:=0;i<left-1;i++{
    pre=pre.Next
  }
  cur:=pre.Next
  for i:=left;i<right;i++{  //翻转链表 直到 right
    next:=cur.Next
    cur.Next=next.Next
    next.Next=pre.Next
    pre.Next=next 
  }
  return head.Next
}

func reverseKGroup( head *ListNode ,  k int ) *ListNode {
    if head==nil||k==1||head.Next==nil{   //特殊情况返回
      return head
    }
    p:=&ListNode{Val:-1,Next:head}
    head=p
    q:=head
    i:=0
    for p.Next!=nil{
      p=p.Next
      i++
      if i==k{    //相等了开始翻转
        xx:=p.Next   //找一个指针让他等于p的后面
        p.Next=nil   //这里断开，不然会搞乱
        Left,Right:=reversNode(q.Next)  //得到左右节点指针
        q.Next=Left   //接上去
        Right.Next=xx
        i=0      //i清空
        p=Right   //放到开头位置
        q=Right
      }
    }
    return head.Next
}
func reversNode(left *ListNode)(Left,Right *ListNode){  //反转链表函数，返回头和尾
  pre:=&ListNode{Val:-1,Next:left}
  left=pre
  pre=left.Next
  q:=pre
  for pre.Next!=nil{
    q=pre.Next
    pre.Next=q.Next
    q.Next=left.Next
    left.Next=q
  }
  return left.Next,pre
}

func Merge( pHead1 *ListNode ,  pHead2 *ListNode ) *ListNode {//把一个链表往另一里面插
    p1:=&ListNode{Val:-1,Next:pHead1}
    pHead1=p1
    q2:=pHead2
    for p1.Next!=nil&&pHead2!=nil{
        if p1.Next.Val<pHead2.Val{ //小则进一步
            p1=p1.Next
        }else{                      //大则 插入  各进一步
            q2=pHead2.Next
            pHead2.Next=p1.Next
            p1.Next=pHead2
            pHead2=q2
            p1=p1.Next
        }
    }
    if pHead2!=nil{                  //看看没完的话 加到后面
        p1.Next=pHead2
    }
    return pHead1.Next
}

func mergeKLists( lists []*ListNode ) *ListNode {
    if len(lists)==0{   //排除特殊值
        return nil
    }
    if len(lists)==1{
        return lists[0]
    }
    pHead1:=lists[0]
    for i:=1;i<len(lists);i++{   //没啥好说的 两两结合
        pHead1=Merge(pHead1,lists[i])
    }
    return pHead1

}
func Merge( pHead1 *ListNode ,  pHead2 *ListNode ) *ListNode {//把一个链表往另一里面插
    p1:=&ListNode{Val:-1,Next:pHead1}
    pHead1=p1
    q2:=pHead2
    for p1.Next!=nil&&pHead2!=nil{
        if p1.Next.Val<pHead2.Val{ //小则进一步
            p1=p1.Next
        }else{                      //大则 插入  各进一步
            q2=pHead2.Next
            pHead2.Next=p1.Next
            p1.Next=pHead2
            pHead2=q2
            p1=p1.Next
        }
    }
    if pHead2!=nil{                  //看看没完的话 加到后面
        p1.Next=pHead2
    }
    return pHead1.Next
}

func hasCycle( head *ListNode ) bool { //快慢指针 有环就会追上相等
    if head==nil{
        return false
    }
    p,q:=head,head.Next
    for p!=nil&&q!=nil&&q.Next!=nil{
        if p==q{
            return true
        }
        p=p.Next
        q=q.Next.Next
    }
    return false
}

//先快慢指针找到有环，然后让p从头节点继续往下走，会在入口点相遇
func EntryNodeOfLoop(pHead *ListNode) *ListNode{
    slow,fast,p:=pHead,pHead,pHead
    for fast!=nil&&fast.Next!=nil{
        slow=slow.Next
        fast=fast.Next.Next
        if slow==fast{   //快慢指针相遇，证明有环
            for fast!=p{   //两个继续走 会在入口点相遇
                fast=fast.Next
                p=p.Next
            }
            return p
        }
    }
    return nil
}

func FindKthToTail( pHead *ListNode ,  k int ) *ListNode {//快慢指针
    pre:=pHead
    i:=0
    for pre!=nil{
        pre=pre.Next
        i++
        if i==k{ //相等就两个同步往后
            s:=pHead
            for pre!=nil{  //为空跳出
                pre=pre.Next
                s=s.Next
            }
            return s  //返回
        }
    }
    return nil  //否则证明k太大，返回nil
}

func removeNthFromEnd( head *ListNode ,  n int ) *ListNode {//快慢指针
    pre:=&ListNode{Val:-1,Next:head} //在他前面加一个
    head=pre
    i:=0
    for pre!=nil{
      pre=pre.Next
      i++
      if i==n{
        slow:=head
        for pre.Next!=nil{ //跳出循环到头了，此时slow 到达它前一个位置
          slow=slow.Next
          pre=pre.Next
        }
        p:=slow.Next
        slow.Next=slow.Next.Next
        p.Next=nil  //释放出来
        return head.Next
      }
    }
    return head.Next
}

func FindFirstCommonNode( pHead1 *ListNode ,  pHead2 *ListNode ) *ListNode {
    if pHead1==nil||pHead2==nil{
        return nil
    }
    p1,p2:=pHead1,pHead2
    for p1!=p2{  //两个链表长度的和是相等的
        if p1==nil{   //一个到头了让他走另一个走过的路
            p1=pHead2
        }else{
            p1=p1.Next
        }
        if p2==nil{
            p2=pHead1
        }else{
            p2=p2.Next
        }
    }
    return p1
}

func addInList( head1 *ListNode ,  head2 *ListNode ) *ListNode {  //翻转链表，从后面加
    head1=reversList(head1)  //翻转
    head2=reversList(head2)
    head:=&ListNode{Val:-1}  //创建链表
    dummy:=head
    ans:=0
    for head1!=nil||head2!=nil||ans!=0{
        if head1!=nil{
            ans=ans+head1.Val
            head1=head1.Next
        }
        if head2!=nil{
            ans=ans+head2.Val
            head2=head2.Next
        }
        dummy.Next=&ListNode{Val: ans%10}  //给Val赋值
        ans=ans/10      //大于10的取余留下来
        dummy=dummy.Next   //往后退 连起来
    }
    return reversList(head.Next)  //最后答案也要翻转
}
func reversList(head *ListNode)*ListNode{ //翻转链表
      if head1==nil{ 
        return nil
    }
    pre:=&ListNode{Val:-1,Next:head}
    head=pre
    pre=pre.Next
    q:=pre
    for pre.Next!=nil{
        q=pre.Next
        pre.Next=q.Next
        q.Next=head.Next
        head.Next=q
    }
    return head.Next
}

func sortInList( head *ListNode ) *ListNode {//二路归并排序
   return sortList(head,nil)
}
func sortList(head,tail *ListNode)*ListNode{ //头和尾 这里尾是空 指下一个
    if head==nil{
        return head
    }
    if head.Next==tail{ //代表只剩下1个值  这一步将链表最终一个一个的单链表 每个只有一个值
        head.Next=nil
        return head
    }
    fast,slow:=head,head
    for fast!=tail&&fast.Next!=tail{ //最快的到达末尾 slow 刚好在中间
        fast=fast.Next
        slow=slow.Next
    }
    mid:=slow
    return merger(sortList(head,mid),sortList(mid,tail))//合并递归   最主要的地方
}
func merger(head1,head2 *ListNode)*ListNode{
    head:=&ListNode{Val:-1}   //新建一个链表
    p:=head
    for head1!=nil&&head2!=nil{   //两个都不为空时
        if head1.Val<=head2.Val{   //那个小就连那个
            head.Next=head1
            head1=head1.Next
        }else{
            head.Next=head2
            head2=head2.Next
        }
        head=head.Next
    }
    if head2!=nil{             //剩余的接上去
        head.Next=head2
    }
    if head1!=nil{
        head.Next=head1
    }
    return p.Next
}

func isPail( head *ListNode ) bool {
    fast,slow:=head,head
    marry:=[]int{}
    for fast!=nil&&fast.Next!=nil{  //找中间值的时候把前半部分放入切片
        marry=append(marry,slow.Val)
        slow=slow.Next
        fast=fast.Next.Next
    }
    if fast!=nil{  //防止总数为奇数，在前进一下
        slow=slow.Next
    }
    for i:=len(marry)-1;i>=0;i--{//按个比较
        if marry[i]!=slow.Val{
            return false
        }
        slow=slow.Next  //记得这里也要后退
    }
    return true
}

func oddEvenList( head *ListNode ) *ListNode {
    if head==nil||head.Next==nil{
        return head
    }
    odd,odd1,even,even1:=head,head,head.Next,head.Next
    for odd!=nil&&odd.Next!=nil&&even!=nil&&even.Next!=nil{  //将奇偶 链表分开
        odd.Next=odd.Next.Next
        odd=odd.Next
        even.Next=even.Next.Next
        even=even.Next
    }
    odd.Next=even1 //把偶接到后面
    return odd1
}

func deleteDuplicates( head *ListNode ) *ListNode {
    if head==nil||head.Next==nil{
      return head
    }
    pre:=head
    for pre!=nil&&pre.Next!=nil{ //往后查
      if pre.Val==pre.Next.Val{ //如果相等
        pre.Next=pre.Next.Next  //让下一个指向下下一个
      }else{
        pre=pre.Next            //如果不想等，再进一步 防止{1,1,1,1}
      }
    }
    return head
}

func deleteDuplicates( head *ListNode ) *ListNode {
    if head==nil||head.Next==nil{
      return head
    }
    p:=&ListNode{Val:-1,Next:head}
    head=p
    q:=p
    x:=false   //标记值，true代表这个数字重复，要去掉
    q=q.Next  //p一直在q的前一个位置
    for q!=nil&&q.Next!=nil{
      if q.Val==q.Next.Val{  //相等 就让q跳到下下一个先去重
        q.Next=q.Next.Next
        x=true
      }else{             //不在重复时
        if x==true{     //看是否有标记
          q=q.Next       //q 正常
          p.Next=p.Next.Next   //如果有，p跳到下下一个
          x=false
        }else{         //如果没有标记 正常后退
          q=q.Next
          p=p.Next
        }
      }
    }
    if x==true{       //看一下有没有遗漏的
      p.Next=p.Next.Next
    }
    return head.Next
}

func search( nums []int ,  target int ) int {
    left,right:=0,len(nums)-1
    mid:=0
    for left<=right{
        mid=left+(right-left)/2    //二分查找精髓
        if nums[mid]==target{
            return mid
        }
        if nums[mid]>target{
            right=mid-1
        }else{
            left=mid+1
        }
    }
    return -1
}

func Find( target int ,  array [][]int ) bool { //关键在于左边的比你小，你下面的比你大，故从右上开始
    m,n:=len(array),len(array[0])
    for i,j:=0,n-1;i<m&&j>=0;{
        if array[i][j]==target{
            return true
        }
        if array[i][j]>target{   //往左下查找
            j--
        }else{
            i++
        }
    }
    return false
}

func findPeakElement(nums []int) int {  //利用二分法
    n := len(nums)
    // 辅助函数，输入下标 i，返回 nums[i] 的值
    // 方便处理 nums[-1] 以及 nums[n] 的边界情况
    get := func(i int) int {     //判断函数，如果是-1或者n,输出最小的值
        if i == -1 || i == n {
            return math.MinInt64
        }
        return nums[i]
    }

    left, right := 0, n-1
    for {
        mid := left+(right-left) / 2
        if get(mid-1) < get(mid) && get(mid) > get(mid+1) {  //如果是则输出
            return mid
        }
        if get(mid) < get(mid+1) {  //不是则改变left和right的值
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
}

func findPeakElement( nums []int ) int {  //跟上面很像
    left,right:=0,len(nums)-1
    i:=0
    for left<right{
        i=left+(right-left)/2  //中间值
        if i-1>-1&&i+1<len(nums){  //判断不在两边的情况
            if nums[i]>nums[i+1]&&nums[i]>nums[i-1]{    
                return i
            }
            if nums[i]<nums[i+1]{
                left=i+1
            }else{
                right=i-1
            }
        }
        if i-1==-1{  //如果在最左边
            if nums[i]>nums[i+1]{
                return i
            }
            left=i+1   //这里++可能退出循环，left==right
        }
        if i+1==len(nums){  //如果在最右边
            if nums[i]>nums[i-1]{
                return i
            }
            right=i-1 //这里--可能退出循环，left==right
        }
    }
    return left  //所以要输入left的值
}

func InversePairs(data []int) int {
	return mergeSort(data, 0, len(data)-1) % 1000000007
}
func mergeSort(data []int, left int, right int) int {
	if left >= right {
		return 0
	}
	mid := left + (right-left)/2
	cnt := mergeSort(data, left, mid) + mergeSort(data, mid+1, right) //计数+分开
	tmp := []int{}
	i, j := left, mid+1 //指向两个数组开头，开始合并
	for i <= mid && j <= right {
		if data[i] <= data[j] {
			tmp = append(tmp, data[i]) //插入
			i++
		} else {
			tmp = append(tmp, data[j])
			cnt = cnt + mid - i + 1 //第一个数组是有序的 此时有mid-i个数比右边大，再+1个
			j++
		}
	}
	for ; i <= mid; i++ { //第一个数组有剩余
		tmp = append(tmp, data[i])
	}
	for ; j <= right; j++ { //第二个数组有剩余
		tmp = append(tmp, data[j])
	}
	for i := left; i <= right; i++ { //要改变data里面排序的结果 赋值
		data[i] = tmp[i-left]
	}
	return cnt
}

func minNumberInRotateArray( rotateArray []int ) int {
    n:=len(rotateArray)
    if n==0{
        return 0
    }
    left,right:=0,n-1
    mid:=0
    for left<right{
        mid=left+(right-left)/2
        if rotateArray[mid]>rotateArray[right]{ //中间比最右边大 一定在右边
            left=mid+1
        }else if rotateArray[mid]<rotateArray[right]{
            right=mid   //不能mid-1，因为有可能mid就是最小的值
        }else{
            right=right-1   //相等的话 减一个 
        }
    }
    return rotateArray[left]
}

func compare( version1 string ,  version2 string ) int {
    n1,n2:=len(version1),len(version2)
    i,j:=0,0
    for i<n1||j<n2{  //双指针
        x:=0
        for ;i<n1&&version1[i]!='.';i++{ //i<n1,且没有到.的时候
            x=x*10+int(version1[i]-'0')
        }
        i++ //跳过.号
        y:=0
        for ;j<n2&&version2[j]!='.';j++{
            y=y*10+int(version2[j]-'0')
        }
        j++ //跳过.号
        if x>y{
            return 1
        }
        if x<y{
            return -1
        }
    }
    return 0    //相等
}

func preorderTraversal( root *TreeNode ) []int {
    marry:=[]int{}
    var preNode func(root *TreeNode)
    preNode=func(root *TreeNode){
        if root==nil{     //为空则返回 要记着
            return
        }
        marry=append(marry,root.Val)
        preNode(root.Left)
        preNode(root.Right)
    }
    preNode(root)
    return marry
}

func inorderTraversal( root *TreeNode ) []int {
    marry:=[]int{}
    var inoderNode func(root *TreeNode)
    inoderNode=func(root *TreeNode){
        if root==nil{
            return
        }
        inoderNode(root.Left)
        marry=append(marry,root.Val)
        inoderNode(root.Right)
    }
    inoderNode(root)
    return marry
}

func postorderTraversal( root *TreeNode ) []int {
    marry:=[]int{}
    var postNode func(root *TreeNode)
    postNode=func(root *TreeNode){
        if root==nil{
            return
        }
        postNode(root.Left)
        postNode(root.Right)
        marry=append(marry,root.Val)
    }
    postNode(root)
    return marry 
}

func levelOrder( root *TreeNode ) [][]int {
    marry:=[][]int{}
    if root==nil{
        return marry
    }
    arry:=[]*TreeNode{}
    arry=append(arry,root)
    for len(arry)>0{
        length:=len(arry)
        ry:=[]int{}
        for i:=0;i<length;i++{
            ry=append(ry,arry[i].Val)
            if arry[i].Left!=nil{
                arry=append(arry,arry[i].Left)
            }
            if arry[i].Right!=nil{
                arry=append(arry,arry[i].Right)
            }
        }
        arry=arry[length:]
        marry=append(marry,ry)
    }
    return marry
}

func Print( pRoot *TreeNode ) [][]int {
    marry:=[][]int{}
    if pRoot==nil{
        return marry
    }
    queue:=[]*TreeNode{}
    queue=append(queue,pRoot)
    arry:=[]int{}
    del:=true
    for len(queue)>0{
        length:=len(queue)
        for i:=0;i<length;i++{
            arry=append(arry,queue[i].Val)
                if queue[i].Left!=nil{
                    queue=append(queue,queue[i].Left)
                } 
                if queue[i].Right!=nil{
                    queue=append(queue,queue[i].Right)
                }    
        }
        queue=queue[length:]
        if del==true{
            marry=append(marry,arry)
            del=!del
        }else{            
            for i,j:=0,len(arry)-1;i<j;i++{   //翻转数组
                arry[i],arry[j]=arry[j],arry[i]
                j--
            }
            marry=append(marry,arry)
        }        
        arry=[]int{} //清空
        del=!del
    }
    return marry
}

func zigzagLevelOrder(root *TreeNode) [][]int {
    marry:=[][]int{}
    if root==nil{
        return marry
    }
    queue:=[]*TreeNode{root}  //创建一个队列 // 当前层
    arry:=[]int{}
    x:=true   // 初始方向
    for len(queue)>0{
        queuelength:=len(queue)
        queue2:= []*TreeNode{} // 构造下一层
        for i:=0;i<queuelength;i++{
            if x==true{
                arry=append(arry,queue[i].Val)
            }else{
                arry=append([]int{queue[i].Val},arry...)// 添加元素到头部
            }
            if queue[i].Left!=nil{
                queue2=append(queue2,queue[i].Left)
            }
            if queue[i].Right!=nil{
                queue2=append(queue2,queue[i].Right)
            }  
        }
        marry=append(marry,arry)
        arry=[]int{}  //清空
        x=!x    //改变方向
        queue=queue2 // 更新当前层
    }
    return marry
}
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.8 MB, 在所有 Go 提交中击败了9.26%的用户

func maxDepth( root *TreeNode ) int {
    if root==nil{
        return 0
    }
    Leftdepth:=maxDepth(root.Left) //左子树深度
    Rightdepth:=maxDepth(root.Right) //右子树深度
    if Leftdepth>Rightdepth{   //那个大
        return Leftdepth+1   //加上本层的
    }
    return Rightdepth+1
}

func hasPathSum( root *TreeNode ,  sum int ) bool {  
    return PathSum(root,0,sum)
}
func PathSum(root *TreeNode,m int,sum int)bool{
   if root==nil{
     return false
   }
    root.Val=root.Val+m
    if root.Left==nil&&root.Right==nil&&root.Val==sum{
      return true
    }
    return PathSum(root.Left,root.Val,sum)||PathSum(root.Right,root.Val,sum)
}

func hasPathSum(root *TreeNode, targetSum int) bool {
    if root==nil{
        return false
    }
    if root.Left==nil&&root.Right==nil{
        return targetSum-root.Val==0
    }
    return hasPathSum(root.Left,targetSum-root.Val)||hasPathSum(root.Right,targetSum-root.Val)
}

//二叉搜索树直接想到中序遍历，把中序遍历先写出来。
func Convert( pRootOfTree *TreeNode ) *TreeNode {
    // write code here
    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        dfs(node.Left)
        //  插入代码
        dfs(node.Right)
    }
    dfs(pRootOfTree)
    return ...
}
//之后有三点需要注意：
//1、当前代码中有什么？——当前代码中只有当前节点。
//2、连接两个节点需要什么？——需要当前节点的前一个节点。
//3、输出结果需要什么？——需要保存head
//所以需要pre和head变量，确定最左下角节点为head，同时也可以确定pre节点，head节点不需要和其他节点连接，所以head后直接右子节点。
//遍历到其他节点时，直接与pre相连
func Convert( pRootOfTree *TreeNode ) *TreeNode {
    var pre, head *TreeNode
    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        dfs(node.Left)
        if pre == nil {
            pre = node
            head = node
        } else {
            pre.Right = node
            node.Left = pre
            pre = node
        }
        dfs(node.Right)
    }
    dfs(pRootOfTree)
    return head
}

func isSymmetrical( pRoot *TreeNode ) bool {
    if  pRoot==nil{
        return true
    }
    return istrical(pRoot.Left,pRoot.Right) 
}
func istrical(Left,Right *TreeNode)bool{
    if Left==nil&&Right==nil{
        return true
    }
    if Left==nil||Right==nil{
        return false
    }
    if Left.Val!=Right.Val{
        return false
    }
    return istrical(Left.Left,Right.Right)&&istrical(Left.Right,Right.Left)
}

func mergeTrees( t1 *TreeNode ,  t2 *TreeNode ) *TreeNode {
    t:=t1
    mergeT(t1,t2)
    return t
}
func mergeT(t1 *TreeNode,t2 *TreeNode){
    if t1==nil&&t2==nil{
        return
    }
    if t1!=nil&&t2==nil{
        return 
    }
    if t1!=nil&&t2!=nil{
        t1.Val=t1.Val+t2.Val
    }
    if t1.Left==nil{ //t1左为空         
        t1.Left=t2.Left  //t2的子树给t1
        t2.Left=nil   //t2断开 
    }
    if t1.Right==nil{ 
        t1.Right=t2.Right
        t2.Right=nil        
    }
    mergeTrees(t1.Left,t2.Left)
    mergeTrees(t1.Right,t2.Right)
}

func Mirror( pRoot *TreeNode ) *TreeNode {
    p:=pRoot
    mirr(pRoot)
    return p
}
func mirr(pRoot *TreeNode){   //巧妙递归
    if pRoot==nil{    //为空则返回
        return 
    }
    pRoot.Left,pRoot.Right=pRoot.Right,pRoot.Left  //转换左右子树
    Mirror(pRoot.Left)  //递归
    Mirror(pRoot.Right)
}

func isValidBST( root *TreeNode ) bool {
    if root==nil{
        return false
    }
    c:=true
    var pre *TreeNode    //从二叉树变双链表学的 建立前指针
    var dfs func(root *TreeNode)
    dfs=func(root *TreeNode){
        if root==nil{
            return
        }
        dfs(root.Left)
        if pre==nil{
            pre=root
        }else{
            if pre.Val>root.Val{  //如果大
                c=false    //改变值
            }else{
                pre=root   //否则 改变pre位置
            }
        }
        dfs(root.Right)
    }
    dfs(root)
    return c
}

func isCompleteTree( root *TreeNode ) bool {  //层序遍历套路
    if root==nil{
        return false
    }
    queue:=[]*TreeNode{}
    queue=append(queue,root)
    sent2:=true
    for len(queue)>0{
        length:=len(queue)
        for i:=0;i<length;i++{
            if queue[i].Left!=nil{    //左不为空
                if sent2==false{    //如果左不为空 右标记 证明下一层了 不行
                    return false
                }
                queue=append(queue,queue[i].Left)   //左加入
                if queue[i].Right!=nil{                    
                    queue=append(queue,queue[i].Right)  //右不为空右加入
                }else{
                    sent2=false  //给一个标记 这一行没完    //如果右为空 给个标记不能再加入了
                }           
            }else{
                if queue[i].Right!=nil{    //如果左为空，右不为空
                    return false
                }else{                       //左为空，右也为空，给个标记 不能再加入了
                    sent2=false
                }
            }      
        }
        queue=queue[length:]
    }
    return true
}

func IsBalanced_Solution( pRoot *TreeNode ) bool {
    if pRoot==nil{
        return true
    }
    if solution(pRoot)==-1{
        return false
    }
    return true   
}
func solution(root *TreeNode)int{
        if root==nil{            //最底层都让他等于1
            return 1
        }
        l:=solution(root.Left)   //左边树高度
        r:=solution(root.Right)  //右边树高度
        if l==-1||r==-1{         //-1就结束了 往上传
            return -1
        }
        if l-r>1||r-l>1{         //超了  就-1
            return -1
        }
        if l>r{
            return l+1   //找最大的+1
        }
        return r+1
}

func lowestCommonAncestor( root *TreeNode ,  p int ,  q int ) int {
    if p>q{     //如果第一个大 交换一下顺序
        p,q=q,p
    }
    var m int   //定义一个记录值
    var cestor func(root *TreeNode,p int,q int)
    cestor=func(root *TreeNode,p int,q int){
        if p<root.Val&&q<root.Val{   //都比根小 记录根  往左
            m=root.Val
            cestor(root.Left,p,q)           
        }
        if p>root.Val&&q>root.Val{   //都比根大，记录根 往右
            cestor(root.Right,p,q)
        }
        if p<root.Val&&q>root.Val{   //一左一右 刚刚好 输出根
            m=root.Val
            return 
        }
        if p==root.Val||q==root.Val{  //相等了  也刚刚好 ，输出
            m=root.Val
            return 
        }
    }
    cestor(root,p,q)
    return m
}

func lowestCommonAncestor(root *TreeNode, o1 int, o2 int) int { //两次查询
	var p, q *TreeNode
	p, q = root, root
	marry1 := lowest(p, o1)
	marry2 := lowest(q, o2)
    n1,n2:=0,0
    if len(marry1)>len(marry2){   //给他排个序
        n1=len(marry1)
        n2=len(marry2)
    }else{
        n2=len(marry1)
        n1=len(marry2)
    }
	for i := 0; i < n1; i++ {  
        if i==n2{                  //这个是防止他前后都一样，例如 9    9，3，4 输出9
            return marry1[i-1]
        }
		if marry1[i] != marry2[i] {
			return marry1[i-1]
		}
	}
	return 0
}
func lowest(root *TreeNode, o int) []int { //找到那个点 并记录他的路径 返回
	marry := []int{}
	x := true
	var find func(root *TreeNode)
	find = func(root *TreeNode) {
		if root == nil {
			marry = append(marry, -1)   //防止回退点时候退过头了
			return
		}
		if x == true {
			marry = append(marry, root.Val)
		}  
		if root.Val == o {           //找到之后给个标识，后面就不继续了
			x = false
			return
		}
		find(root.Left)
		if x == true {
			marry = marry[:len(marry)-1]  //回退
		}
		find(root.Right)
		if x == true {
			marry = marry[:len(marry)-1]
		}
	}
	find(root)
	return marry
}

func lowestCommonAncestor(root *TreeNode, o1 int, o2 int) int { //递归
    if root == nil {   //到底了返回-1
        return -1
    }
    if root.Val == o1|| root.Val == o2 {  //找到了 返回root.val
        return root.Val
    }
    left := lowestCommonAncestor(root.Left, o1, o2)
    right := lowestCommonAncestor(root.Right, o1, o2)
    if left != -1 && right != -1 {  //证明左右子树都返回的不是-1两边都找到了 返回
        return root.Val
    }
    if left == -1 {  //左边找到了返回左边 左边没找到返回右边
        return right
    }
    return left
}

func reConstructBinaryTree( pre []int ,  vin []int ) *TreeNode {
    if len(pre)==0||len(vin)==0{
        return nil
    }
    n:=findnode(vin,pre[0])//在中序遍历中找到前序遍历的第一个值的位置
    root:=&TreeNode{       //递归构造树
        Val:pre[0],
        Left:reConstructBinaryTree(pre[1:n+1],vin[:n]),  //注意pre[1:n+1]他的左子树就是到n+1
        Right:reConstructBinaryTree(pre[n+1:],vin[n+1:]), //不要写成pre[1:] 后面就不管了
    }
    return root
}
func findnode(vin []int,n int)int{  //找到他返回下标，方便下面分割
    for i:=0;i<len(vin);i++{
        if vin[i]==n{
            return i
        }
    }
    return -1
}

func solve( xianxu []int ,  zhongxu []int ) []int {  //构建二叉树加层序遍历
    root:=treeNode(xianxu,zhongxu)
    arry:=[]int{}
    if root==nil{       //开始层序遍历
        return arry
    }
    queue:=[]*TreeNode{}
    queue=append(queue,root)
    for len(queue)>0{   //注意这里条件
        length:=len(queue)
        arry=append(arry,queue[length-1].Val)    //输出最右边的
        for j:=0;j<length;j++{           
            if queue[j].Left!=nil{
                queue=append(queue,queue[j].Left)
            }
            if queue[j].Right!=nil{
                queue=append(queue,queue[j].Right)
            }
        }        
        queue=queue[length:]
    }  
    return arry
}
func treeNode(xianxu []int ,  zhongxu []int)*TreeNode{ //构建树
    if len(xianxu)==0||len(zhongxu)==0{
        return nil
    }
    n:=find(zhongxu,xianxu[0])    
    root:=&TreeNode{
        Val:xianxu[0],
        Left:treeNode(xianxu[1:n+1],zhongxu[:n]),
        Right:treeNode(xianxu[n+1:],zhongxu[n+1:]),
    }
    return root
}
func find(zhongxu []int,val int)int{   //查找根节点在中序遍历中的位置
    for i:=0;i<len(zhongxu);i++{
        if zhongxu[i]==val{
            return i
        }
    }
    return -1
}

package main
var stack1 [] int
var stack2 [] int
func Push(node int) {   //入栈就是其中一个入
    stack1=append(stack1,node)
}
func Pop() int{    //出的时候 如果第二个不为空，出第二个，如果第二个为空，将第一个全部放到第二个，然后出
    if len(stack2)>0{
        m:=stack2[len(stack2)-1]
        stack2=stack2[:len(stack2)-1]
        return m
    }else{   //如果stack2为空
        for i:=len(stack1)-1;i>=0;i--{
            stack2=append(stack2,stack1[i])        
        }
        stack1=[]int{}
        n:=stack2[len(stack2)-1]
        stack2=stack2[:len(stack2)-1]
        return n
    }
}

package main
var stack []int
func Push(node int) {
    stack=append(stack,node)
}
func Pop() {
    stack=stack[:len(stack)-1]
}
func Top() int {
    m:=stack[len(stack)-1]
    return m
}
func Min() int {
    if len(stack)>0{
        m:=stack[0]
        for i:=1;i<len(stack);i++{
            if m>stack[i]{
                m=stack[i]
            }
        }
        return m
    }
    return 0
}

func isValid( s string ) bool {
    marry:=[]byte{}
    for _,i:=range s{
      if byte(i)=='('||byte(i)=='['||byte(i)=='{'{
        marry=append(marry,byte(i))
      }else{
        if len(marry)==0{ //如果栈空，就得到}，返回false
          return false
        }
        if marry[len(marry)-1]=='('&&byte(i)==')'||marry[len(marry)-1]=='['&&byte(i)==']'||marry[len(marry)-1]=='{'&&byte(i)=='}'{   //如果成对 出栈      
              marry=marry[:len(marry)-1]
        }else{  //不成对 返回false
          return false
        }
      }
    }
    if len(marry)!=0{  //如果栈不为空返回false
      return false
    }
    return true
}

type Stack struct {            //定义栈
	size int
	top  int
	data []string
}
func isValid(s string) bool {
	s1 := Stack{}                  //初始化栈
	s1.size = len(s)
	s1.top = -1
	s1.data = make([]string, len(s))
	for _, a := range s {             //遍历s
		var b string
		if string(a) == ")" {           //设置出栈条件
			b = "("
		}
		if string(a) == "}" {
			b = "{"
		}
		if string(a) == "]" {
			b = "["
		}
		if s1.top > -1 && s1.data[s1.top] == b { //相等出栈
			s1.top--
		} else {                                //不等入栈
			s1.top++
			s1.data[s1.top] = string(a)
		}
	}
	if s1.top == -1 {                             //判断栈空为true
		return true
	} else {
		return false
	}
}

func maxInWindows(num []int, size int) []int {
	marry := []int{}
	if size > len(num) || size == 0 {
		return marry
	}
	if size == 1 {
		return num
	}
	queue := []int{}
	queue = append(queue, num[0])
	max := num[0]               //最大值
	x := 0                      //最大值下标
	for i := 1; i < size; i++ { //第一个滑块插入队列
		queue = append(queue, num[i])
		if num[i] > max {
			max = num[i]
			x = i
		}
	}
	marry = append(marry, max) //第一个滑块的最大值先加进去
	for i := size; i < len(num); i++ {
		queue = queue[1:]
		queue = append(queue, num[i])
		if i-x < size { //证明它没出去
			if num[i] > max {
				max = num[i]
				x = i
			}
		} else {
			max, x = find(queue, i)  //查找最大值和下标
		}
		marry = append(marry, max)  //加入最大值
	}
	return marry
}
func find(queue []int, n int) (max int, x int) {   //这样搞如果全是递减的话 时间复杂度就超了
	maxc := queue[0]
	xx := 0
	for i := 1; i < len(queue); i++ {
		if queue[i] > maxc {
			maxc = queue[i]
			xx = i
		}
	}
	return maxc, n - (len(queue) - 1) - xx
}

func maxInWindows(num []int, size int) []int {
	  marry := []int{}
    if size==0||len(num)==0||size>len(num){
        return marry
    }
	  queue := []int{}
    var push func(i int) //插入队列
    push=func(i int){  //你是大的就循环把你前面小的拿走 //因为小的没用
		for len(queue)>0&&num[i]>num[queue[len(queue)-1]]{ //如果比最右边大，则把最右的拿出来，再加入，比你小直接加入，比你大的话你就没用了 ，比你小怕你下一个就出去
            queue=queue[:len(queue)-1]
        }
        queue = append(queue, i)  //下标插进去 
    }
    for i:=0;i<size;i++{ //现将前几个都插入
        push(i)
    }
    marry=append(marry,num[queue[0]]) //第一个最大值插入
    for i:=size;i<len(num);i++{
        push(i)
        for queue[0]<=i-size{ //看你是不是被划出去了 如果是，队列退出一个
            queue=queue[1:]
        }
        marry=append(marry,num[queue[0]])
    }
	return marry
}

func GetLeastNumbers_Solution( input []int ,  k int ) []int {
    arry:=[]int{}
    length:=len(input)
    if k==0{
        return arry
    }
    if k>length||k==length{
        return input
    }
    for i:=0;i<k;i++{  //将前k个数写入arry
        arry=append(arry,input[i])
    }
    arry=heapScortMax(arry) //先做大根堆
    for j:=k;j<length;j++{ //从k开始往后
        if input[j]<arry[0]{  //遇到小的
            arry[0]=input[j]  //替换里面最大的
            arry=heapScortMax(arry) //调整堆
        }
    }
    return arry
}
func heapScortMax(arry []int)[]int{
    length:=len(arry)
    depth:=length/2-1
    for i:=depth;i>=0;i--{
        topmax:=i
        left:=i*2+1 //左子树
        right:=i*2+2 //右子树
        if left<=length-1&&arry[left]>arry[topmax]{
            topmax=left  //找到最大值
        }
        if right<=length-1&&arry[right]>arry[topmax]{
            topmax=right //找到最大值
        }
        if topmax!=i{
            arry[i],arry[topmax]=arry[topmax],arry[i]  //跟父节点做交换
        }
    }
    return arry
}

func findKth( a []int ,  n int ,  K int ) int {
    // write code here
    sort(a,0,n-1) //快速排序
    return a[K-1]
}
func sort(arry []int, left, right int) { //数组，左右下标
    if left>=right{  //防止越界
        return
    }
    i:=left
    j:=right
    topmax:=arry[i]  //定义topmax
    for i<j{
        for i<j&&arry[j]<topmax{ //后面的比较小
            j--   //继续
        }
        if i<j{ //arry[j]>=topmax  //证明后面比较大
            arry[i]=arry[j]  //换位置
            i++
        }
        for i<j&&arry[i]>topmax{  //前面比较大
            i++         //继续
        } 
        if i<j{  //arry[i]<=topmax  //换位置
            arry[j]=arry[i]
            j--
        }
    }
    arry[i]=topmax
    sort(arry,left,i-1)  //递归 
    sort(arry,i+1,right)
}

package main
import "sort"
var arry []int
func Insert(num int){
	arry=append(arry, num)
}
func GetMedian() float64{
	length:=len(arry)
    sort.Ints(arry) //排序  快速排序的时间复杂度为O(nlogn) 或者这里可以写个快排
    if length%2==0{
        return float64(arry[length/2]+arry[(length/2)-1])/2 //偶数时，中间相加/2
    }else{
        return float64(arry[length/2])  //奇数时，中间
    }
}