首页 线上实习 课程 找实习 必考题 咨询 专栏 组团学 稳拿计划
校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 数据结构 > 栈
题目

递归式的先序遍历一个n节点，深度为d的二叉树，需要栈空间的大小为

A.O（n）

B.O（d）

C.O（logn）

D.O（nlogn）

上一题 下一题
解答

正确答案是 B

因为二叉树并不一定是平衡的，也就是深度d！=logn，有可能d>>logn。。所以栈大小应该是O（d）

C 8条回复 评论
fearless

又学到了~~

发表于 2021-12-27 17:49:27
0 0
fearless

又学到了~~

发表于 2021-12-27 17:49:26
0 0
芝麻酱

强~~希望更多人更加努力

发表于 2021-09-13 08:00:00
0 0
假期

正确答案是b

发表于 2021-03-27 22:38:54
0 0
窦先生

二叉树深度d满足：logn<=d<=n，所以需要栈空间大小O(d)

发表于 2018-10-13 10:35:22
0 0
花花

我想问一下，不是非递归才用栈吗？递归用栈干嘛啊？？？

发表于 2018-10-13 10:35:14
0 0
小小小可乐

因为二叉树并不一定是平衡的，也就是深度d！=logn，有可能d > > logn(远大于)，所以栈大小应该是O（d）

发表于 2018-10-13 10:35:01
0 0
站桩灵

在从根向下遍历中，每次先转移到左子树上，而右边则需要暂存起来，因此，最多需要的暂存空间需要d个

发表于 2018-10-13 10:34:56
0 0
问题信息
分类：数据结构 - 栈
难度:
最新校招难题刷题，快来进刷题群吧
相关试题