将有序索引分配给二叉树

Question

我们如何为二叉树分配有序索引？

给定下面的一棵树：

      1
   2      3
4    5  6   7

将下面的索引分配给上面的树，如下所示：

      4
   2      6
1    3  5    7

以下代码不适用于案例 6，因为它分配了 10，因为我们正在双重计算从参数和左子节点向下传递的索引。我们可以不使用全局变量来实现吗？

  int assignIndex(Node root, int index) {
        if (root == null)
            return 0;

        int leftIndex = assignIndex(root.left, index);

        root.index = leftIndex + index + 1;

        int rightIndex = assignIndex(root.right, root.index);

        if (rightIndex == 0)
            return root.index;
        else
            return rightIndex;
    }

Answer 1

上面程序的问题是return在两个不同的场合有两个不同的值。因此，如果您不想使用全局变量，可以通过 return 在任何情况下仅使用最新的索引值来解决此问题。

int assignIndex(Node root, int index) {

    if (root.left != null)
       index = assignIndex(root.left, index);  

    index++;
    root.index = index;

    if (root.right != null)
       index = assignIndex(root.right, index);

    return index;

}

将有序索引分配给二叉树

Assign in-order index to Binary Tree

algorithm

binary-tree

data-structures

array-algorithms