我要招人

去企业版

首页 > 试题广场 >

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

[单选题]

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

```
O(n)
```
```
O(d)
```
```
O(log(n))
```
```
O(n*log(n))
```

推荐

牛客-007

答案：B

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

编辑于 2015-02-04 15:58:41 回复(1)

Aix码哥

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

发表于 2015-07-01 16:34:34 回复(4)

Radar

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

发表于 2015-09-09 10:05:07 回复(0)

阳光下的米雪

本题中，由于没有明确交代二叉树的类型或性质，本题中的二叉树是无法确定类型的，自然而然也就并不一定是平衡的了，也就是说，深度d的值并不一定等于logn，很有可能d的值比logn的值大，而栈空间的大小通常为二叉树的深度，因此，栈的大小应该是O(d)，而不是O(logn)。所以，本题的答案为B。

发表于 2019-06-01 11:34:51 回复(0)

翻红的番茄

每遍历一个左树就会把相应的右树压入栈内存起来，直到左边没有树了，才开始弹栈

发表于 2020-01-06 21:00:54 回复(0)

牛客吴彦祖QAQ

根结点入栈，弹出栈顶，输出，如果有子节点，分别入右孩子，左孩子。弹出栈顶，输出。。。循环。。。。。

发表于 2017-05-20 11:11:05 回复(0)

薛定谔之喵

完全二叉树深度d=logN+1,题目未说明是否为完全二叉树

编辑于 2016-03-07 10:53:17 回复(0)

hptc

非递归的先序遍历：先根进出栈，子节点再先右后左入栈

发表于 2019-09-27 15:51:36 回复(0)

rickkcir

每次对二叉树进行先序遍历时，都会递归调用先处理当前节点，然后分别对左子树和右子树进行先序遍历。每个递归调用都会在栈上创建一个新的栈帧（stack frame，也是一种栈）用于存储函数的状态信息（例如参数、返回地址等），这些栈帧的数量与递归深度直接相关。

递归深度与树的深度有直接关系，在最坏的情况下，如果二叉树是一个完全不平衡的树（只有左子树或只有右子树），递归深度将等于树的深度。因此，树的深度决定了递归调用的层数，所以栈大小应该是O(d)。

编辑于 2023-12-04 15:51:28 回复(0)

不想等待

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

发表于 2022-07-11 20:01:03 回复(0)

wanlanwalan

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

发表于 2017-03-29 11:31:10 回复(0)

小郑同学ye

发表于 2023-11-15 15:58:23 回复(0)

冰㒱沝

根入栈，出栈，输出如果有左孩子，递归遍历起左孩子，再次递归其右孩子所以递归其全部的左孩子至少需要O（d）

发表于 2023-06-08 15:00:05 回复(0)

梦境迷离

非AVL 坑爹了

发表于 2018-01-12 17:14:31 回复(0)

丁宇龙945

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

发表于 2017-11-20 17:28:19 回复(3)

sunlight_run

二叉树并不一定是平衡的，d != logn，所以需要空间为O（d）

发表于 2017-06-12 20:36:44 回复(0)

xingshanxie

退化为链表

发表于 2017-03-02 20:52:51 回复(0)

wentguo

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

编辑于 2016-05-16 09:17:44 回复(0)

幻影迷风

需要栈空间的大小，只是一个概念上的大小，不管具体的大小，在一个二叉树中，按照先序遍历，为0（d）

发表于 2015-08-27 14:58:23 回复(0)

提交观点

问题信息

栈阿里巴巴树

上传者：sometimes

难度：

19条回答 1997收藏 13615浏览

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

问题信息

热门推荐

相关试题