Diameter of Binary Tree


@woofyzhao Generally yes, as usually Big O is most often discussed (compared to omega and theta)

@jocelynayoga Both examples are technically correct, your O(H) one is more precise though.

@Mr.Bin We calculated the number of nodes in the path, but the length is 1 minus this number. For example ABC there are 3 nodes but it is length 2.

Why the solution with global variable is welcome on leetcode?
Everyone know, it's a bad practice. And at the real interview, is better to think about code design and good practices as well, besides time and space complexity.
Here is the solution without recursion and global variable:class Solution {
public int diameterOfBinaryTree(TreeNode root) {
if (root == null) {
return 0;
}Stack<TreeNode> stack = new Stack<>(); Map<TreeNode, Integer> maxLengthMap = new HashMap<>(); stack.push(root); int maxDiameter = 0; boolean explored = false; while (stack.size() != 0) { TreeNode node = stack.peek(); explored = (node.left != null && maxLengthMap.containsKey(node.left))  node.left == null; if (!explored && node.left != null) { stack.push(node.left); } explored &= (node.right != null && maxLengthMap.containsKey(node.right))  node.right == null; if (!explored && node.right != null) { stack.push(node.right); } //System.out.println("explored  " + explored + ", node val  " + node.val); if (explored) { int leftLength = maxLengthMap.getOrDefault(node.left, 0); if (node.left != null) { leftLength += 1; } int rightLength = maxLengthMap.getOrDefault(node.right, 0); if (node.right != null) { rightLength += 1; } //System.out.println(" leftLength  " + leftLength + ", rightLength  " + rightLength); maxLengthMap.put(node, Math.max(leftLength, rightLength)); int diameter = leftLength + rightLength; if (maxDiameter < diameter) { maxDiameter = diameter; } stack.pop(); } } return maxDiameter; }
}

Why u call "Depth" here? Should we call it as the "height"?
https://stackoverflow.com/questions/2603692/whatisthedifferencebetweentreedepthandheight
https://en.wikipedia.org/wiki/Tree_(data_structure)Correct me if I am wrong.

My solution without using a global variable.
class Solution { private class Int { int val; Int(int val) { this.val = val; } } public int diameterOfBinaryTree(TreeNode root) { if (root == null) return 0; Int ans = new Int(0); depthOfTree(root, ans); return ans.val; } public int depthOfTree(TreeNode root, Int ans) { if (root == null) return 0; int l = depthOfTree(root.left, ans); int r = depthOfTree(root.right, ans); ans.val = Math.max(ans.val, l + r); return 1 + Math.max(l, r); } }
