Find Largest Value in Each Tree Row | Tree Problem | LeetCode 515
4 years ago Lalit Bhagtani 0
Problem Statement
You have given a binary tree, write a program to find out the largest value in each row of a given binary tree.
Example
Input : [5, 3, 8, 2, 4, null, 9] Result : [5, 8, 9].
Solution
To solve this problem, we have to find out the largest value at each level. The solution can be implemented using both depth first search and breadth first search algorithm.
Breadth First Search
import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; public class Main { public static void main(String[] args) { Main main = new Main(); TreeNode node = new TreeNode(5); node.left = new TreeNode(3); node.right = new TreeNode(8); node.left.left = new TreeNode(2); node.left.right = new TreeNode(4); node.right.right = new TreeNode(9); List<Integer> result = main.largestValues(node); result.forEach(System.out::print); } public List<Integer> largestValues(TreeNode root) { List<Integer> result = new ArrayList<>(); if(root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); int size, i, value; while(queue.size() > 0){ value = Integer.MIN_VALUE; size = queue.size(); for(i=0; i<size; i++){ root = queue.poll(); if(value < root.val){ value = root.val; } if(root.left != null) queue.add(root.left); if(root.right != null) queue.add(root.right); } result.add(value); } return result; } public static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } }
Depth First Search
import java.util.ArrayList; import java.util.List; public class Main { public static void main(String[] args) { Main main = new Main(); TreeNode node = new TreeNode(5); node.left = new TreeNode(3); node.right = new TreeNode(8); node.left.left = new TreeNode(2); node.left.right = new TreeNode(4); node.right.right = new TreeNode(9); List<Integer> result = main.largestValues(node); result.forEach(System.out::print); } public List<Integer> largestValues(TreeNode root) { List<Integer> result = new ArrayList<>(); if(root == null) return result; dfs(root, 0, result); return result; } public void dfs(TreeNode node, int level, List<Integer> result){ if(node == null) return; if(result.size() == level){ result.add(node.val); }else { if(result.get(level) < node.val){ result.set(level, node.val); } } dfs(node.left, level+1, result); dfs(node.right, level+1, result); } public static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } }
Result
589
Similar Post
That’s all for Find Largest Value in Each Tree Row in Java, If you liked it, please share your thoughts in a comments section and share it with others too.