java - 转换原始二叉树以将其装饰为预排序索引

Question

我试了一下，它适用于左子树，但不适用于右子树。

我很接近，但我的逻辑是错误的，任何人都可以帮助纠正并解释这个逻辑。

public static MyNode preOrderNumbering(MyNode n) {
            if (n != null) {
                n.obj = 0; // Set root decoration to 0;
                preOrderHelper(n, 1); // Set decorations according to preorder.
            }
            return n;
        }

        public static MyNode preOrderHelper(MyNode n, int counter) {
            if (n != null) {
                if (n.left != null) {
                    n.left.obj = counter++; // Set the left object decoration to current count + 1;
                    preOrderHelper(n.left, counter);
                }
                if (n.right != null) {
                    n.right.obj = counter++; // Set the left object decoration to current count + 1;
                    preOrderHelper(n.right, counter);
                }
            }
            return n;
        }

前：

后：

Answer 1

counter在left转到right. _

像这样的东西：

public static int preOrderNumbering(MyNode n, int count){
    if(n != null){
        n.obj = ++count;

        count = preOrderNumbering(n.left, count);
        count = preOrderNumbering(n.right, count);

    }
    return count;
}

Answer 2

您是counter按值传递，而不是按引用传递（因为这就是 Java 的工作方式），因此当递归展开时，计数器也将展开。

您可以通过从递归调用返回当前值来更新计数器。