中序遍历 || Call Stack space 可以考虑（或）不行吗？
Inorder Traversal || Call Stack space to be considered (or) Not?
这个查询已经在我脑海中萦绕了很多天，我希望有人能够清除它。
问题：- 找出二叉树中的节点数
方法 1：-（迭代）
使用栈进行中序遍历。每当您从堆栈中弹出元素时，请记下它的计数，即二叉树中的节点数。
时间复杂度 - O(n)
Space 复杂度 - O(n)
方法 2：-（递归）
时间复杂度 - O(n)
Space 复杂度 - O(1) 或 O(n)?????
我们可以递归地进行中序遍历，但是在面试中，向面试官表达哪种方法是最佳的.....迭代还是递归？？我还应该考虑将 space 复杂度归结为 O(n) 的递归调用堆栈 space 还是应该坚持 O(1) Space 复杂度？
你的问题 - "which approach would be optimal expressing to the interviewer" - 除了面试官自己，其他人都无法真正回答。但是，解决这个问题的可能方法之间的差异值得讨论。
首先，请注意迭代和递归方法都使用堆栈；迭代方法有一个显式堆栈，但递归函数使用 call stack 工作，这不是由程序员管理的。因此，两种方法使用的辅助 space 将 渐近地 相同，但迭代方法的常数较低，因为它仅将节点推入堆栈，而递归方法推送整个调用帧，包括所有局部变量。
注意辅助space是O(h) 其中h是树的高度，不是O (n) 其中 n 是节点数。这很重要，因为最坏的情况将取决于当树的高度太大时树是否为 balanced. For an unbalanced tree, the height h is O(n) in the worst case, whereas for a balanced tree, h is O(log n). The question doesn't specify that the tree is balanced, so there is a risk that the recursive approach will overflow the stack。相比之下，迭代方法在主内存中存储一个显式堆栈。
以上都是关于效率的讨论，但是编程比算法效率更重要。例如，如果树永远不会很大，您可能更喜欢递归方法，因为它编写起来简单得多；它只需要几行非常干净的代码。命令式方法需要创建一个堆栈，并在循环中从中压入和弹出，因此代码可能会更长且更难理解。不要低估干净、易于理解的代码的价值。
还有一点就是你直接跳到中序遍历作为解题，但是如果题是统计二叉树的节点个数，那么你可以任意顺序遍历.与中序遍历相比，先序遍历在迭代实现上更简单一些，而且同样高效。
或者，如果可以修改数据结构本身，那么直接给每个节点一个 属性 来保存其子树的基数。需要修改插入、删除和重新平衡操作以维护此 属性，但额外的工作是 O(1)，它允许通过简单读取在 O(1) 中计算树的大小根节点的基数 属性。添加这个 属性 还有其他好处，例如支持 O(h) 时间的 "find the kth node" 操作而不是 O(h + k).
这个查询已经在我脑海中萦绕了很多天，我希望有人能够清除它。 问题：- 找出二叉树中的节点数
方法 1：-（迭代） 使用栈进行中序遍历。每当您从堆栈中弹出元素时，请记下它的计数，即二叉树中的节点数。
时间复杂度 - O(n)
Space 复杂度 - O(n)
方法 2：-（递归）
时间复杂度 - O(n)
Space 复杂度 - O(1) 或 O(n)?????
我们可以递归地进行中序遍历，但是在面试中，向面试官表达哪种方法是最佳的.....迭代还是递归？？我还应该考虑将 space 复杂度归结为 O(n) 的递归调用堆栈 space 还是应该坚持 O(1) Space 复杂度？
你的问题 - "which approach would be optimal expressing to the interviewer" - 除了面试官自己，其他人都无法真正回答。但是，解决这个问题的可能方法之间的差异值得讨论。
首先，请注意迭代和递归方法都使用堆栈；迭代方法有一个显式堆栈，但递归函数使用 call stack 工作，这不是由程序员管理的。因此，两种方法使用的辅助 space 将 渐近地 相同，但迭代方法的常数较低，因为它仅将节点推入堆栈，而递归方法推送整个调用帧，包括所有局部变量。
注意辅助space是O(h) 其中h是树的高度，不是O (n) 其中 n 是节点数。这很重要，因为最坏的情况将取决于当树的高度太大时树是否为 balanced. For an unbalanced tree, the height h is O(n) in the worst case, whereas for a balanced tree, h is O(log n). The question doesn't specify that the tree is balanced, so there is a risk that the recursive approach will overflow the stack。相比之下，迭代方法在主内存中存储一个显式堆栈。
以上都是关于效率的讨论，但是编程比算法效率更重要。例如，如果树永远不会很大，您可能更喜欢递归方法，因为它编写起来简单得多；它只需要几行非常干净的代码。命令式方法需要创建一个堆栈，并在循环中从中压入和弹出，因此代码可能会更长且更难理解。不要低估干净、易于理解的代码的价值。
还有一点就是你直接跳到中序遍历作为解题，但是如果题是统计二叉树的节点个数，那么你可以任意顺序遍历.与中序遍历相比，先序遍历在迭代实现上更简单一些，而且同样高效。
或者，如果可以修改数据结构本身，那么直接给每个节点一个 属性 来保存其子树的基数。需要修改插入、删除和重新平衡操作以维护此 属性，但额外的工作是 O(1)，它允许通过简单读取在 O(1) 中计算树的大小根节点的基数 属性。添加这个 属性 还有其他好处，例如支持 O(h) 时间的 "find the kth node" 操作而不是 O(h + k).