如何避免在这里使用全局变量?

Question

所以问题是找到二叉树的直径。我的方法是，对于每个节点，找到左节点的高度和右节点的高度。然后，如果高度(左节点(+ 1(对于当前节点(+高度(右节点(大于当前最大直径，我将更新最大直径。我最初为此使用全局变量，但改为使用大小为 1(int[] 直径(的数组。我知道这很笨拙，不是有人在编程面试中欣赏的东西，所以有人有更好的建议吗？我知道在C中我只能使用指针，但不幸的是，我对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];
}

Answer 1

您可以使用此代码来解决您的问题：

// 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());
}
}

Answer 2

您可以使用AtomicInteger方法的任何更改都会影响调用方

public static int height(TreeNode node, AtomicInteger max) {
if (node == null) {
return 0;
}
int leftHeight = height(node.left, max);
int rightHeight = height(node.right, max);
max.set(Math.max(max.intValue(), leftHeight + 1 + rightHeight));
return 1 + Math.max(leftHeight, rightHeight);
}
public int diameter(TreeNode root) {
AtomicInteger max;
height(root, max);
return max.intValue();
}