访谈问：二叉树有序遍历

Question

我是在一次采访中被问到这个问题的。

问题：给出了一个二叉树和相应子树的高度。然后我们必须按顺序找到一个特定位置的元素。

例如：树结构为：D（根节点）[subtree-size=6]-->B,F（D的子节点）[subtree-size=2]-->A,C,E,G（叶节点）[subtree-size=0]。

因此共有3个级别：级别0:D；1级：B级、F级；2级:A、C、E、G

我们必须在inorder中计算特定顺序/位置的节点，例如p。如果p=2，则节点为B（有序遍历）。

我的解决方案：我建议我们需要做一次顺序遍历（通过BFS/DFS)，然后我们可以给出第I个顺序节点，时间复杂度将是O(n)。

Answer 1

如果我们想在顺序遍历中找到第i个位置的元素：

• 如果左子树正好有i-1节点，我们知道我们正在查找根。
• 如果左子树有i或更多节点，我们知道它将在左子树中。
• 我们知道如果左子树的节点少于i-1,则它将位于右子树中。
• 我们可以通过适当地更新i来递归地重复这一操作。更具体地说，我们需要将i减小左子树的大小加上右子树的大小，因为该子树的顺序遍历将从原始顺序遍历的那个位置开始。当转到左侧子树时，我们不需要更改i，因为该子树的顺序遍历将从原始顺序遍历的起始位置开始。

所以，在伪代码中，我们可以做到以下几点：

currentNode = root
while true
  if getSubtreeCount(currentNode.left) == i-1
    return currentNode
  else if getSubtreeCount(currentNode.left) < i-1
    currentNode = currentNode.left
  else
    currentNode = currentNode.right
    i -= getSubtreeCount(currentNode.left) + 1

这将为我们提供o(treeHeight)的运行时间。

示例：

假设我们有一棵树：

     D
   /   \
  B     F
 / \   / \
A   C E   G