将节点值更改为二叉树的高度

Question

我的任务是在二叉树中将节点的值更改为其高度。根据任务的条件，您需要在树的1次传递中更改所有值，但是您可以使用其他数据结构来违反此条件。我有一个代码，但无法正常工作。 This is the original tree，here is what I want to get，and this is the result of the program written below

public void replaceValuesToHeight() {
    ArrayDeque<TreeNode> leftTreeQueue = new ArrayDeque<>();
    ArrayDeque<TreeNode> rightTreeQueue = new ArrayDeque<>();
    rightTreeQueue.add(getRoot());
    replaceValuesToHeight(getRoot(), new ArrayDeque<>(), new ArrayDeque<>(), leftTreeQueue, rightTreeQueue, 0, 0, true);
}

public int replaceValuesToHeight(TreeNode node, ArrayDeque<ArrayDeque<TreeNode>> leftTree, ArrayDeque<ArrayDeque<TreeNode>> rightTree, ArrayDeque<TreeNode> leftTreeQueue, ArrayDeque<TreeNode> rightTreeQueue, int maxLeft, int maxRight, boolean isLeft) {
    if (node == null) {
        leftTree.add(leftTreeQueue);
        rightTree.add(rightTreeQueue);
        leftTreeQueue.clear();
        rightTreeQueue.clear();
        return 0;
    }

    if (isLeft)
        leftTreeQueue.add(node);

    maxLeft = replaceValuesToHeight(node.getLeft(), leftTree, rightTree, leftTreeQueue, rightTreeQueue, ++maxLeft, maxRight, true);

    if (!isLeft)
        rightTreeQueue.add(node);


    maxRight = replaceValuesToHeight(node.getRight(), leftTree, rightTree, leftTreeQueue, rightTreeQueue, maxLeft, ++maxRight, false);


    int depth = 1 + Math.max(maxLeft, maxRight);

    if (node == getRoot()) {
        leftTree.clear();
        rightTree.clear();
    }

    node.value = depth;

    //rightTreeQueue = rightTree.poll();
    //leftTreeQueue = leftTree.poll();


    if (maxLeft > maxRight) {
        int i = 0;
        while (!rightTreeQueue.isEmpty()) {
            rightTreeQueue.poll().value = maxLeft - i;
            i++;
        }
        //leftTreeQueue.clear();
    } else if (maxRight > maxLeft) {
        int i = 0;
        while (!leftTreeQueue.isEmpty()) {
            leftTreeQueue.poll().value = maxRight - i;
            i++;
        }
        //rightTree.clear();
    }

    return depth;
}

Answer 1

如果TreeNode是

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}

我认为递归解决方案会更好：

static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return toString(1);
    }

    private String toString(int tabs) {
        String indent = Collections.nCopies(tabs, " ").stream().collect(Collectors.joining());
        return String.format("%d, %n%sl:%s,%n%sr:%s", val,
            indent, left != null ? left.toString(tabs + 1) : "null",
            indent, right != null ? right.toString(tabs + 1) : "null");
    }
}

public static void main(String[] args) {

    TreeNode root = new TreeNode(0,
        new TreeNode(0,
            new TreeNode(0,
                null,
                new TreeNode(0,
                    null,
                    null)),
            null),
        new TreeNode(0,
            null,
            null));

    System.out.println(root);
    setHeights(root, 0);
    System.out.println(root);
}

private static void setHeights(TreeNode node, int h) {
    if (node == null) return;
    node.val = h;
    setHeights(node.left, h + 1);
    setHeights(node.right, h + 1);
}

打印：

0, 
 l:0, 
  l:0, 
   l:null,
   r:0, 
    l:null,
    r:null,
  r:null,
 r:0, 
  l:null,
  r:null
0, 
 l:1, 
  l:2, 
   l:null,
   r:3, 
    l:null,
    r:null,
  r:null,
 r:1, 
  l:null,
  r:null