java 如何计算二叉搜索树中每个节点的深度？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/30777766/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to calculate depth of each node in Binary Search Tree?
提问by Gregg
My task is to calculate depth of each node and store it in 'depth' given in Node class. But I don't know how I should approach this task. I was looking for some example in the internet but haven't found any appropriate to my task. This is the code of my given Node class:
我的任务是计算每个节点的深度并将其存储在 Node 类中给出的“深度”中。但我不知道我应该如何处理这个任务。我在互联网上寻找一些例子，但没有找到任何适合我的任务。这是我给定的 Node 类的代码：
Node
{int value; Node left, right; int depth;}
I thought I could use a similar method to counting height of a tree but it didn't work out. Any help?
我以为我可以使用类似的方法来计算树的高度，但没有成功。有什么帮助吗？
采纳答案by Zereges
void updateDepth(Node node, int depth)
{
if (node != null)
{
node.depth = depth;
updateDepth(node.left, depth + 1); // left sub-tree
updateDepth(node.right, depth + 1); // right sub-tree
}
}
Call with updateDepth(root, 0);
与 updateDepth(root, 0);
回答by tucuxi
Most algorithms on binary trees work by recursion - you check a base condition to see if recursion should stop, and then you do your thing for the left and right children, possibly accumulating what you find. In this case,
二叉树上的大多数算法都是通过递归工作的——你检查一个基本条件，看看递归是否应该停止，然后你为左右孩子做你的事情，可能会累积你找到的东西。在这种情况下，
static void addDepth(Node n, int currentDepth) {
if (n == null) return; // check base condition
// store current depth in this node
n.setDepth(currentDepth);
// recursion
addDepth(left, currentDepth+1);
addDepth(right, currentDepth+1);
}
Or, alternatively (assuming that addDepthis part of your Nodeclass):
或者，或者（假设这addDepth是您Node班级的一部分）：
void addDepth(int current) {
depth = current;
if (left != null) left.addDepth(current+1);
if (right != null) right.addDepth(current+1);
}
Both versions are equivalent. In the second, I am checking the base condition right before recursion, instead of (as is done in the 1st version) right before looking at the node.
两个版本是等价的。在第二个中，我在递归之前检查基本条件，而不是在查看节点之前（如第一个版本中所做的那样）。
