fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. class TreeNode {
  8.  
  9.   public int val;
  10.   public TreeNode left;
  11.   public TreeNode right;
  12.  
  13.   public TreeNode(int x) {
  14.     val = x;
  15.   }
  16. }
  17. /* Name of the class has to be "Main" only if the class is public. */
  18. class Ideone
  19. {
  20. 	public int diameterOfBinaryTree(TreeNode root) {
  21.  
  22.     Map<TreeNode, Integer> map = new HashMap<>();
  23.     Stack<TreeNode> stack = new Stack<>();
  24.     int diameter = 0;
  25.  
  26.     if (root != null)
  27.       stack.push(root);
  28.  
  29.     while (!stack.isEmpty()) {
  30.       TreeNode node = stack.peek();
  31.  
  32.       // Fill up stack to perform post-order traversal
  33.       if (node.left != null && !map.containsKey(node.left)) {
  34.         stack.push(node.left);
  35.       } else if (node.right != null && !map.containsKey(node.right)) {
  36.         stack.push(node.right);
  37.       } else {
  38.  
  39.         // Process the root, once left and right sub-tree have been processed
  40.         stack.pop();
  41.         int leftDepth = map.getOrDefault(node.left, 0);
  42.         int rightDepth = map.getOrDefault(node.right, 0);
  43.  
  44.         // Put the max depth at a node in the map
  45.         map.put(node, 1 + Math.max(leftDepth, rightDepth));
  46.  
  47.         // Update the max diameter found so far
  48.         diameter = Math.max(diameter, leftDepth + rightDepth);
  49.       }
  50.     }
  51.     return diameter;
  52.   }
  53.  
  54. 	public static void main (String[] args) throws java.lang.Exception
  55. 	{
  56. 		Ideone diameterOfABinaryTree = new Ideone();
  57. 		// your code goes here
  58. 		//
  59.     //       1
  60.     //      / \
  61.     //     2   3
  62.     //    / \
  63.     //   4   5
  64.     TreeNode root = new TreeNode(1);
  65.     root.left = new TreeNode(2);
  66.     root.left.left = new TreeNode(4);
  67.     root.left.right = new TreeNode(5);
  68.     root.right = new TreeNode(3);
  69.  
  70.     System.out.println(diameterOfABinaryTree.diameterOfBinaryTree(root));
  71. 	}
  72. }
Success #stdin #stdout 0.06s 32364KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/6YOUm0
language:
Java (12.0.1)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!