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

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

如果树节点是

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

递归求解。基本上，您需要在处理左子树时了解右子树，反之亦然。节点的结果值可传递地取决于最低叶。这意味着您需要扫描整棵树才能找到它（n 操作），然后才能为节点赋值。

所以这取决于您对 "single-pass" 的要求有多强（对树进行单次迭代，仅此而已？或者在最后进行适当的调整，使其成为 2*n ~= O(n)） .

static class TreeNodeDepth {
    TreeNode node;
    int depth;
    public TreeNodeDepth(TreeNode node, int depth) { ... }
}

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) {
        if (left == null && right == null) return val + "";
        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 = buildExampleTree();

    PriorityQueue<TreeNodeDepth> maxHeap = new PriorityQueue<>(
        Comparator.<TreeNodeDepth>comparingInt(n -> n.depth).reversed()
    );
    System.out.println(root);

    setHeights(root, 0, maxHeap);
    int max = maxHeap.peek().depth; // check for: at least one element exists
    while (!maxHeap.isEmpty()) {
        TreeNodeDepth depthNode = maxHeap.poll();
        depthNode.node.val = max - depthNode.depth + 1;
    }

    System.out.println(root);
}

private static void setHeights(TreeNode node, int h, PriorityQueue<TreeNodeDepth> maxHeap) {
    if (node == null) return;
    maxHeap.add(new TreeNodeDepth(node, h));
    setHeights(node.left, h + 1, maxHeap);
    setHeights(node.right, h + 1, maxHeap);
}

打印：

-

8, 
 l:3, 
  l:2, 
   l:1,
   r:null,
  r:1,
 r:7, 
  l:null,
  r:6, 
   l:1,
   r:5, 
    l:null,
    r:4, 
     l:null,
     r:3, 
      l:null,
      r:2, 
       l:null,
       r:1
8, 
 l:7, 
  l:6, 
   l:5,
   r:null,
  r:6,
 r:7, 
  l:null,
  r:6, 
   l:5,
   r:5, 
    l:null,
    r:4, 
     l:null,
     r:3, 
      l:null,
      r:2, 
       l:null,
       r:1

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

Change node values to their heights in a binary tree

java

algorithm

tree

binary-tree