java - 如何避免在这里使用全局变量?
问题描述
所以问题是找到二叉树的直径。我的方法是,对于每个节点,找到左节点的高度和右节点的高度。如果 height(left node) + 1 (for current node) + height(right node) 大于当前最大直径,我然后更新最大直径。我最初为此使用了一个全局变量,但改为使用大小为 1(int[] 直径)的数组。我知道这很hacky,在编程面试中可能不会有人欣赏,所以有人有更好的建议吗?我知道在 CI 中可以只使用指针,但不幸的是我没有使用 Java 的奢侈。
public static int height(TreeNode node, int[] diameter) {
if (node == null) {
return 0;
}
int leftHeight = height(node.left, diameter);
int rightHeight = height(node.right, diameter);
diameter[0] = Math.max(diameter[0], leftHeight + 1 + rightHeight);
return 1 + Math.max(leftHeight, rightHeight);
}
public int diameter(TreeNode root) {
int[] diameterArr = new int[1];
int heightRoot = height(root, diameterArr);
return diameterArr[0];
}
解决方案
您可以使用此代码解决您的问题:
// Recursive optimized Java program to find the diameter of a
// Binary Tree
/* Class containing left and right child of current
node and key value*/
class Node
{
int data;
Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
/* Class to print the Diameter */
class BinaryTree
{
Node root;
/* Method to calculate the diameter and return it to main */
int diameter(Node root)
{
/* base case if tree is empty */
if (root == null)
return 0;
/* get the height of left and right sub trees */
int lheight = height(root.left);
int rheight = height(root.right);
/* get the diameter of left and right subtrees */
int ldiameter = diameter(root.left);
int rdiameter = diameter(root.right);
/* Return max of following three
1) Diameter of left subtree
2) Diameter of right subtree
3) Height of left subtree + height of right subtree + 1 */
return Math.max(lheight + rheight + 1,
Math.max(ldiameter, rdiameter));
}
/* A wrapper over diameter(Node root) */
int diameter()
{
return diameter(root);
}
/*The function Compute the "height" of a tree. Height is the
number f nodes along the longest path from the root node
down to the farthest leaf node.*/
static int height(Node node)
{
/* base case tree is empty */
if (node == null)
return 0;
/* If tree is not empty then height = 1 + max of left
height and right heights */
return (1 + Math.max(height(node.left), height(node.right)));
}
public static void main(String args[])
{
/* creating a binary tree and entering the nodes */
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.println("The diameter of given binary tree is : "
+ tree.diameter());
}
}
推荐阅读
- java - 使用 Google Cloud 对本地 Spring Boot 服务进行身份验证
- c++ - Clang 预编译标头 - 使用不同的 /usr/include 时间戳 - 也许通过编辑元数据?
- go - 使用 pprof 配置 kubectl
- python - Python CSV多值列到多行
- azure-devops - Devops Multistage Pipeline 只需要一次批准
- flutter - 居中的旋转木马,不会在颤动中卡住
- amazon-web-services - 缩小 RDS 实例会保留数据吗?
- sql - 有没有办法以特定的日期频率(例如工作日)查询表?
- angular - 当我使用 Angular Material 日期选择器时,我的页面停止显示
- vue.js - vue js 3 路由不起作用 - 不改变路由