递归式的先序遍历一个n节点,深度为d的二叉树,需要栈空间的大小为
A.O(n)
B.O(d)
C.O(logn)
D.O(nlogn)
正确答案是 B
因为二叉树并不一定是平衡的,也就是深度d!=logn,有可能d>>logn。。所以栈大小应该是O(d)
又学到了~~
强~~希望更多人更加努力
正确答案是b
二叉树深度d满足:logn<=d<=n,所以需要栈空间大小O(d)
我想问一下,不是非递归才用栈吗?递归用栈干嘛啊???
因为二叉树并不一定是平衡的,也就是深度d!=logn,有可能d > > logn(远大于),所以栈大小应该是O(d)
在从根向下遍历中,每次先转移到左子树上,而右边则需要暂存起来,因此,最多需要的暂存空间需要d个
从浏览器输入URL到展示页面的全流程是怎么样的?
使用js实现数组的冒泡排序
小程序没有分享到朋友圈的功能,但是产品为了推广,需要曲线实现这个功能,请给出设计方案?
微信公众号中服务号和订阅号合二为一,你怎么看?
又学到了~~
又学到了~~
强~~希望更多人更加努力
正确答案是b
二叉树深度d满足:logn<=d<=n,所以需要栈空间大小O(d)
我想问一下,不是非递归才用栈吗?递归用栈干嘛啊???
因为二叉树并不一定是平衡的,也就是深度d!=logn,有可能d > > logn(远大于),所以栈大小应该是O(d)
在从根向下遍历中,每次先转移到左子树上,而右边则需要暂存起来,因此,最多需要的暂存空间需要d个