fb arraybuild min heap 题

fb有一道题是给一个int array, 给这个array建一个min heap的树，并且这个树的中序遍历的结果跟原array相同
这里提供一个时间和空间都是o(n)的解法，
对于一个升序的array e.g. 1 2 3 4 5 这个树只能是1
\
  2
    \
     3
      \
       4
        \
         5
对于一个降序的array e.g 5 4 3 2 1 这个树只能是
     1
     /                                                         
    2
    /
   3
   /
  4
/
5                          
从这两个例子就启发用stack来解这个题
TreeNode

{
  int val;
  TreeNode left;
  TreeNode right;
}

public TreeNode buildMinHeap(int[] array)

{

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

align="left">                s.push(n);

        }

        while(s.size() > 1)

        {

                s.pop();

        }

        return s.pop();

}

求指正，随便来点大米哈

min heap 有两个性质，1：根节点小于等于他的孩子，2：必须是一颗完全树，依在下看来，楼主给的两个单调递增和单调递减情况生成的树并非min heap tree，因为他们并不满足性质二，也就是complete tree这点，我好想知道这个问题的准确描述在哪里，楼主您能否给予相关链接呢？

s.peek().val < array －_－> ???

apollopffd 发表于 2017-1-30 13:46
s.peek().val < array －_－> ???

array[i]

apollopffd 发表于 2017-1-30 13:46
s.peek().val < array －_－> ???

txt copy过来的，显然这是一个格式问题

挺tricky的算法，谢谢分享。不过显然不是O(n) runtime吧 顶多是O(nlgn)或者最坏就是O(n2)

zjiang42 发表于 2017-2-1 06:05
挺tricky的算法，谢谢分享。不过显然不是O(n) runtime吧 顶多是O(nlgn)或者最坏就是O(n2)

哈哈 很显然是o(n)的，每个treenode都push一次，pop一次

byrlhb 发表于 2017-2-1 08:17
哈哈 很显然是o(n)的，每个treenode都push一次，pop一次

还真是，拜服一下这个解法

WhatsFLAG 发表于 2017-2-1 15:53
min heap 有两个性质，1：根节点小于等于他的孩子，2：必须是一颗完全树，依在下看来，楼主给的两个单调递 ...

说的没错哦，但是如果是完全树，中序遍历是不可能是原array的，你理解意思就好

zjiang42 发表于 2017-2-1 11:13
还真是，拜服一下这个解法

给点加分哈