数据结构有哪些类型和特点？

本文共计1488个文字，预计阅读时间需要6分钟。

今天，接续上一期的文章，继续推进！下面是代码，要求求一棵树的深度，为什么需要存储起来呢？在解答这个问题之前，我们需要稍微改动一下上面的代码。下面是改动后的代码：

pythondef tree_depth(node): if not node: return 0 left_depth=tree_depth(node.left) right_depth=tree_depth(node.right) return max(left_depth, right_depth) + 1

这段代码会发现问题所在。上述代码中，每个节点都会被访问两次：一次在计算左子树的深度，一次在计算右子树的深度。因此，对于一棵有n个节点的树，每个节点都会被访问n次，导致算法的时间复杂度为O(n^2)。这是非常低效的。

现在我们来解答为什么需要存储起来。实际上，在计算树的深度时，我们并不需要存储整个树的结构，而是只需要记录下到达每个节点的路径长度。这样，我们就可以避免重复访问节点，从而将时间复杂度降低到O(n)。下面是修改后的代码：

pythondef tree_depth(node): if not node: return 0 stack=[(node, 1)] # 使用栈来存储节点和路径长度 max_depth=0 while stack: node, depth=stack.pop() max_depth=max(max_depth, depth) if node.left: stack.append((node.left, depth + 1)) if node.right: stack.append((node.right, depth + 1)) return max_depth

这段代码使用了一个栈来记录到达每个节点的路径长度。在遍历过程中，我们只需要更新最大深度即可。这样，我们就避免了重复访问节点，使得算法的时间复杂度降低到O(n)。