Binary Tree Çap Hesabı

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.

https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/529/week-2/3293/

>> Solution 1 - Use DFS with Recursion

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	import java.util.*;
	class BinaryTreeDiameterCalculatorWithRecursion {
	public int diameterOfBinaryTree(TreeNode root) {
	SolutionFinder finder = new SolutionFinder();
	findDepth(root, finder);
	return finder.value;
	}
	/**
	*
	*/
	private int findDepth(TreeNode currentRoot, SolutionFinder finder){
	if(currentRoot==null) {
	return 0;
	}
	// Calculate the depth of a node in the usual way
	// max(depth of node.left, depth of node.right) + 1
	int leftDepth = findDepth(currentRoot.left, finder);
	int rightDepth = findDepth(currentRoot.right, finder);
	int currentDepth = 1 + Math.max(leftDepth,rightDepth);
	// Check if current diameter is the maximum and save it
	int currentDiameter = leftDepth + rightDepth;
	finder.suggestDiameter(currentDiameter);
	return currentDepth;
	}
	private class SolutionFinder {
	private int value = 0;
	private void suggestDiameter(int currentDiameter){
	if(this.value < currentDiameter) {
	this.value = currentDiameter;
	}
	}
	}
	}

view raw BinaryTreeDiameterCalculatorWithRecursion.java hosted with ❤ by GitHub

>> Solution 2 - Use Post Order DFS with Two Stacks

See

• https://www.geeksforgeeks.org/dfs-traversal-of-a-tree-using-recursion/
• https://www.geeksforgeeks.org/iterative-postorder-traversal/ 

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	import java.util.*;
	class BinaryTreeDiameterCalculatorWithStack {
	public int diameterOfBinaryTree(TreeNode root) {
	if(root == null) {
	return 0;
	}
	int diameter = -1;
	Map<TreeNode,TreeNodeInfo> nodeInfoMap = new HashMap<>();
	Stack<TreeNodeInfo> s1 = new Stack<>();
	Stack<TreeNodeInfo> s2 = new Stack<>();
	// Postorder DFS Traversal (Left, Right, Root)
	s1.push(new TreeNodeInfo(root));
	while(!s1.isEmpty()) {
	TreeNodeInfo current = s1.pop();
	s2.push(current);
	if(current.left != null) {
	s1.push(current.left);
	}
	if(current.right != null) {
	s1.push(current.right);
	}
	}
	while(!s2.isEmpty()) {
	TreeNodeInfo current = s2.pop();
	// Traversal Action
	current.setDiameter(current.getLeftNodeDepth() + 1, current.getRightNodeDepth() + 1);
	if(diameter < current.diameter){
	diameter = current.diameter;
	}
	}
	return diameter;
	}
	private class TreeNodeInfo {
	// TreeNode node;
	TreeNodeInfo left;
	TreeNodeInfo right;
	int depth;
	int diameter;
	TreeNodeInfo(TreeNode node){
	// this.node = node;
	this.left = node.left == null ? null : new TreeNodeInfo(node.left);
	this.right = node.right == null ? null : new TreeNodeInfo(node.right);
	}
	int getLeftNodeDepth(){
	return left == null ? -1 : left.depth;
	}
	int getRightNodeDepth(){
	return right == null ? -1 : right.depth;
	}
	void setDiameter(int leftDepth, int rightDepth){
	this.depth = Math.max( leftDepth, rightDepth);
	diameter = leftDepth + rightDepth;
	}
	}
	}

view raw BinaryTreeDiameterCalculatorWithStack.java hosted with ❤ by GitHub