Блог пользователя Bliss8

Автор Bliss8, 7 лет назад, По-английски

Given a problem:
find diameter of binary tree (diameter is longest possible path between any two nodes in a tree)
Node format:

public class TreeNode {
    TreeNode left;
    TreeNode right;
}

External variable approach:

int maxDiameter = 0; //we will update this external variable from recursion calls
public int diameterOfBinaryTree(TreeNode root) {
    explore(root);
    return maxDiameter;
}

public int explore(TreeNode node) {
    if (node == null) {
        return 0;
    }
    int left = explore(node.left);
    int right = explore(node.right);
    maxDiameter = Math.max(maxDiameter, left + right);
    return Math.max(left, right) +  1;
}

Composite return approach:
To solve this task in clear functional way, without external variables, need to return information about max diameter found instead of updating a variable. As now it's needed to return 2 values (max diameter found and depth), will simply return int[].

public int diameterOfBinaryTree(TreeNode root) {
    return explore(root)[1];
}

public int[] explore(TreeNode node) {
    if (node == null) {
        return new int[]{0, 0};
    }
    int[] left = explore(node.left);
    int[] right = explore(node.right);
    int maxDepth = Math.max(left[0], right[0]);
    int maxDiameter = Math.max(Math.max(left[1], right[1]), left[0] + right[0]);
    return new int[]{maxDepth + 1, maxDiameter};
}

Which approach do you prefer?
From my point of view, if mutability is acceptable, external variable is the way to go.

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится