如何计算二叉搜索树的深度
我想计算二进制搜索树的每个节点的深度的总和。
元素的各个深度尚未存储。
像这样的东西：
int countChildren(Node node) { if ( node == null ) return 0; return 1 + countChildren(node.getLeft()) + countChildren(node.getRight()); } 并获得每个孩子的深度总和：
int sumDepthOfAllChildren(Node node, int depth) { if ( node == null ) return 0; // starting to see a pattern? return depth + sumDepthOfAllChildren(node.getLeft(), depth + 1) + sumDepthOfAllChildren(node.getRight(), depth + 1); }
现在有一个希望提供信息的解释，以防这是家庭作业。 计算节点数非常简单。 首先，如果节点不是节点（ node == null ），则返回0.如果它是节点，则首先计算其自身（ 1 ），加上其左子树中的节点数加上右子树中的节点数。 另一种思考方式是通过BFS访问每个节点，并为您访问的每个节点添加一个计数。
深度的总和是类似的，除了不为每个节点仅添加一个，该节点添加其自身的深度。 它知道自己的深度，因为它的父母告诉它。 每个节点都知道它的子节点的深度是它自己的深度加一，所以当你得到一个节点的左右子节点的深度时，你告诉它们它们的深度是当前节点的深度加1。
而且，如果节点不是节点，则它没有深度。 因此，如果您想要所有根节点的子节点的深度总和，则传递根节点和根节点的深度，如下所示： sumDepthOfAllChildren(root, 0)
递归是非常有用的，它只是一种非常不同的思考方式，并使实践习惯于它
int maxDepth(Node node) { if (node == null) { return (-1); // an empty tree has height −1 } else { // compute the depth of each subtree int leftDepth = maxDepth(node.left); int rightDepth = maxDepth(node.right); // use the larger one if (leftDepth > rightDepth ) return (leftDepth + 1); else return (rightDepth + 1); } }
对于任何给定的树，根的节点数为1加上左子树中的节点数加上右子树中的节点数:)
确保实际存在左或右子树的细节“留给读者”。
这种解决方案更加简单。
public int getHeight(Node root) { if(root!=null) return 1+ Math.max(getHeight(root.leftchild),getHeight(root.rightchild)); else return 0; }
private static int getNumberOfNodes(Node node) { if (node == null) { return 0; } return 1 + getNumberOfNodes(node.left) + getNumberOfNodes(node.right); }
public class Node { private Node left; private Node right; public int size() { return 1+ (left==null?0:left.size())+ (right==null?0:right.size());} }
int depth(treenode *p) { if(p==NULL)return(0); if(p->left){h1=depth(p->left);} if(p=>right){h2=depth(p->right);} return(max(h1,h2)+1); }
public int numberOfNodes() { // This node. int result = 1; // Plus all the nodes from the left node. Node left = getLeft(); if (left != null) result += left.numberOfNodes(); // Plus all the nodes from the right node. Node right = getRight(); if (right != null) result += right.numberOfNodes(); return result; }
public int countNodes(Node root) { // Setup // assign to temps to avoid double call accessors. Node left = root.getLeft(); Node right = root.getRight(); int count = 1; // count THIS node. // count subtrees if (left != null) count += countNodes(left); if (right != null) count += countNodes(right); return count; }
public int getDepthHelper( TreeNode< T > node ) { int treeHeightLeft; int treeHeightRight; //get height of left subtree if( node.leftNode == null ) treeHeightLeft = 1; else { treeHeightLeft = getDepthHelper( node.leftNode) + 1; } //get height of right subtree if( node.rightNode == null ) treeHeightRight = 1; else { treeHeightRight = getDepthHelper( node.rightNode) + 1; } return Math.max(treeHeightLeft, treeHeightRight); }