查找二叉树的第n个有序节点，其中每个节点在其子树中包含左节点数

Question

我遇到了这个问题，似乎在任何地方都找不到解决办法。

给定一个二叉树，其中每个节点都包含一个数字，表示其子树中剩余节点的数量，编写一个函数，返回第n个按顺序遍历的节点。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.leftNodes = 0

查找按序遍历的第n个节点相当简单，但如何使用关于左节点数的信息来改进该过程？

Answer 1

正如@m69给出的提示，您可以使用左节点计数来避免一些不必要的步骤。

假设有一棵树，其中根在他的左侧子树中有10个节点：然后当询问第n个节点时（按顺序排列时），如果n=1-10，则答案将在左侧子树。但是如果n=11，则答案将是根，否则答案将在右侧子树中。

考虑以下伪代码：

findNnode(TreeNode root, int n) {
    if (root.leftNodes + 1 == n )
        return root; 
    if (root.leftNodes <= n)
        return findNnode(root.left, n)
    newN = n - root.leftNodes - 1; // after substract all node who came before in in-order
    return findNnode(root.right, newN)
}  

希望这有帮助！