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

Question

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

Given a binary tree where each node contains a number denoting the amount of left nodes in its subtree, write a function that returns the nth inorder traversal node.

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

找到 nth node of inorder traversal 相当简单，但我如何使用有关左节点数的信息来改进过程？

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)
}

希望对您有所帮助！

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

Finding nth inorder node of a binary tree where each node contains number of left nodes in its subtree

algorithm

binary-tree