package com.freetymekiyan.algorithms.level.easy;

import com.freetymekiyan.algorithms.utils.Utils.TreeNode;

/**
 * 543. Diameter of Binary Tree
 * <p>
 * Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the
 * length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
 * <p>
 * Example:
 * Given a binary tree
 * |     1
 * |    / \
 * |   2   3
 * |  / \
 * | 4   5
 * Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
 * <p>
 * Note: The length of path between two nodes is represented by the number of edges between them.
 * <p>
 * Related Topics: Tree
 */
public class DiameterOfBinaryTree {

    /**
     * Recurrence relation:
     * Diameter of the current tree can be:
     * 1. Cross root, height(left) + height(right)
     * 2. Not cross root, the maximum of diameters of left and right subtrees.
     * Has some duplicate calculations.
     */
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int crossRoot = height(root.left) + height(root.right);
        int leftDiameter = diameterOfBinaryTree(root.left);
        int rightDiameter = diameterOfBinaryTree(root.right);
        return Math.max(Math.max(crossRoot, leftDiameter), rightDiameter);
    }

    private int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(height(root.left), height(root.right));
    }

    /**
     * Get the diameter of each node then return the maximum.
     * Diameter of each node is left + right.
     */
    public int diameterOfBinaryTree2(TreeNode root) {
        int[] result = new int[1]; // A bit of hack. Pass int array by reference to avoid field variable.
        height(root, result);
        return result[0];
    }

    private int height(TreeNode root, int[] maxD) {
        if (root == null) {
            return 0;
        }
        int l = height(root.left, maxD);
        int r = height(root.right, maxD);
        if (l + r > maxD[0]) maxD[0] = l + r;
        return (l > r ? l : r) + 1;
    }
}

@@ -746,236 +746,219 @@
 ecur
-rence relation:%0A     * Diameter of the current tree can be:%0A     * 1. Cross root, height(left) + height(right)%0A     * 2. Not cross root, the maximum of diameters of left and right subtrees.%0A     * Has some duplicate calculations
+sive. DFS.%0A     * Get the diameter of each node then return the maximum.%0A     * Diameter = depth(left subtree) + depth(right subtree).%0A     * Maintain an 1-element array to hold the reference of maximum diameter
 .%0A  
@@ -998,16 +998,17 @@
 naryTree
+2
 (TreeNod
@@ -1030,318 +1030,140 @@
    i
-f (root == null) %7B%0A            return 0;%0A        %7D%0A        int crossRoot = height(root.left) + height(root.right);%0A        int leftDiameter = diameterOfBinaryTree(root.left);%0A        int rightDiameter = diameterOfBinaryTree(root.right);%0A        return Math.max(Math.max(crossRoot, leftDiameter), rightDiameter)
+nt%5B%5D diameter = new int%5B1%5D; // A bit of hack. Pass int array hold reference.%0A        dfs(root, diameter);%0A        return diameter%5B0%5D
 ;%0A  
@@ -1175,38 +1175,35 @@
     private int 
-height
+dfs
 (TreeNode root) 
@@ -1192,32 +1192,41 @@
 fs(TreeNode root
+, int%5B%5D d
 ) %7B%0A        if (
@@ -1285,189 +1285,482 @@
     
-return 1 + Math.max(height(root.left), height(root.right));%0A    %7D%0A%0A    /**%0A     * Get the diameter of each node then return the maximum.%0A     * Diameter of each node is 
+int l = dfs(root.left, d);%0A        int r = dfs(root.right, d);%0A        if (l + r %3E d%5B0%5D) d%5B0%5D = l + r;%0A        return (l %3E r ? l : r) + 1;%0A    %7D%0A%0A    /**%0A     * Recursive.%0A     * Recurrence relation:%0A     * Diameter is the # of edges of the longest path between 2 nodes.%0A     * If two nodes are in the same tree, the diameter is the larger the the two subtrees' diameters.%0A     * If not, the diameter is the depth(
 left
+)
  + 
-right
+depth(right).%0A     * Has some duplicate calculations
 .%0A  
@@ -1792,33 +1792,32 @@
 eterOfBinaryTree
-2
 (TreeNode root) 
@@ -1831,159 +1831,322 @@
    i
-nt%5B%5D resul
+f (roo
 t =
+=
  n
-ew int%5B1%5D; // A bit of hack. Pass int array by reference to avoid field variable.%0A        height(root, result);%0A        return result%5B0%5D
+ull) %7B%0A            return 0;%0A        %7D%0A        int crossRoot = getDepth(root.left) + getDepth(root.right);%0A        int leftDiameter = diameterOfBinaryTree(root.left);%0A        int rightDiameter = diameterOfBinaryTree(root.right);%0A        return Math.max(Math.max(crossRoot, leftDiameter), rightDiameter)
 ;%0A  
@@ -2166,22 +2166,24 @@
 ate int 
-height
+getDepth
 (TreeNod
@@ -2192,20 +2192,8 @@
 root
-, int%5B%5D maxD
 ) %7B%0A
@@ -2264,22 +2264,36 @@
     
-int l = height
+return 1 + Math.max(getDepth
 (roo
@@ -2302,139 +2302,32 @@
 left
+)
 , 
-maxD);%0A        int r = height(root.right, maxD);%0A        if (l + r %3E maxD%5B0%5D) maxD%5B0%5D = l + r;%0A        return (l %3E r ? l : r) + 1
+getDepth(root.right))
 ;%0A  
@@ -2331,9 +2331,8 @@
 %0A    %7D%0A%7D
-%0A

update 543. Diameter of Binary Tree