Binary Tree Zigzag Level Order Traversal LeetCode Java

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

Solution:-


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 import java.util.*;
public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        HashMap<Integer,LinkedList<Integer>> map = new HashMap<Integer,LinkedList<Integer>> ();
        traverse(root, 1 , map);
        for(int i = 1 ; i <=map.size() ; i++){
            LinkedList<Integer> temp = map.get(i);
         
            if(temp != null){
                List<Integer> item = new ArrayList<Integer>();
                item.addAll(temp);
                res.add(item);
            }
        }
        return res;
     
    }
 
    private void traverse(TreeNode root, int level, HashMap<Integer,LinkedList<Integer>> map){
        if(root != null){
         
            if(map.containsKey(level))
            {
                LinkedList<Integer> temp = map.get(level);
                if(level % 2 == 0){
                    temp.addFirst(root.val);
                }
                else{
                    temp.addLast(root.val);
                }
                map.put(level,temp);
             
            }
            else{
                LinkedList<Integer> link = new LinkedList<Integer>();
                link.add(root.val);
                map.put(level,link);
            }
            level++;
         
            traverse(root.left, level, map);
            traverse(root.right, level, map);
         
        }
     
    }
}

LeetCode Java : Populating Next Right Pointers in Each Node

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Solution:

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
 
    HashMap<Integer,List<TreeLinkNode>> map = new HashMap<Integer,List<TreeLinkNode>>();
    traverse(root, map , 0);
    }
 
    private void traverse(TreeLinkNode root, HashMap<Integer,List<TreeLinkNode>> map , int level){
     
        if(root != null){
         
            if(map.containsKey(level)){
                List<TreeLinkNode> temp = map.get(level);
                TreeLinkNode set = temp.get(temp.size() -1 );
                set.next = root;
                root.next = null;
                temp.add(root);
                map.put(level,temp);
            }
            else{
                root.next = null;
                List<TreeLinkNode> temp = new ArrayList<TreeLinkNode>();
                temp.add(root);
                map.put(level,temp);
            }
            level++;
            traverse(root.left, map , level);
            traverse(root.right, map,level);
         
         
        }
    }
}

Binary Tree Right Side View LeetCode Java

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

Solution:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
     
        List<Integer> res = new ArrayList<Integer>();
        HashMap<Integer,List<Integer>> map = new HashMap<Integer, List<Integer>>();
    traverse(root,map, 0);
 
    for(int i = 0 ; i < map.size() ; i++){
        List<Integer> temp = map.get(i);
        if(temp != null){
            res.add(temp.get(temp.size() -1));
        }
    }
    return res;
     
    }
 
    private void traverse(TreeNode root, HashMap<Integer,List<Integer>> map, int level ){
 
    if(root != null){
     
        if(map.containsKey(level)){
            List<Integer> temp = map.get(level);
            temp.add(root.val);
            map.put(level,temp);
        }
        else{
            List<Integer> temp = new ArrayList<Integer>();
            temp.add(root.val);
            map.put(level,temp);
        }
        level++;
        traverse(root.left,map,level);
        traverse(root.right,map,level);
     
    }
    }
}

Longest Even Length Substring such that Sum of First and Second Half is same

Given a string ‘str’ of digits, find length of the longest substring of ‘str’, such that the length of the substring is 2k digits and sum of left k digits is equal to the sum of right k digits. 

Examples:

Input: str = "123123"
Output: 6
The complete string is of even length and sum of first and second
half digits is same

Input: str = "1538023"
Output: 4
The longest substring with same first and second half sum is "5380"

Solution:

public class Solution{

public static void main(String [] args)
{
String val = "1538023";
int [][] dp = new int[val.length() ][val.length() ];

for(int i = 0 ; i < val.length(); i++){
dp[i][i] = Integer.valueOf(val.charAt(i));
}
int max = 0 ;
for(int c = 2 ; c < val.length() ; c++){
for(int i = 0 ; i < val.length() - c + 1 ; i++){
int j = i + c - 1;
int k = c / 2;
dp[i][j] = dp[i][j-1] + Integer.valueOf(val.charAt(j));
if(c % 2 == 0 && dp[i][j - k] == dp[j-k+1][j] && c > max){
max = c;
}


}
}
System.out.println(max);
}

}

Binary Tree Level Order Traversal II LeetCode Java

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

Solution:-

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        HashMap<Integer,List<Integer>> map = new HashMap<Integer,List<Integer>>();
        traversal(root,map, 0);
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int level = map.size();
        for(int i = level ; i >=0 ; i--){
            List<Integer> temp = map.get(i);
            if(temp != null){
                res.add(temp);
            }
        }
       
        return res;
    }
   
    private void traversal(TreeNode root, HashMap<Integer,List<Integer>> map, int level){
       
        if(root != null){
            if(map.containsKey(level)){
                List<Integer> temp = map.get(level);
                temp.add(root.val);
                map.put(level,temp);
            }
            else{
                List<Integer> temp = new ArrayList<Integer>();
                temp.add(root.val);
                map.put(level,temp);
            }
            traversal(root.left, map, level + 1);
            traversal(root.right, map, level + 1);
           
           
        }
       
       
       
    }
}

Implement Trie (Prefix Tree) Leet Code Java Solution

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

Solution:-


class TrieNode {
   
    public TrieNode [] children;
    public boolean isLeaf;
    // Initialize your data structure here.
    public TrieNode() {
        children = new TrieNode[26];
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode temp = root;
        int length = word.length();
        for(int level = 0 ; level < length ; level ++){
           
            if(temp.children[word.charAt(level) - 'a'] == null){
                temp.children[word.charAt(level) - 'a'] = new TrieNode();
               
            }
            temp = temp.children[word.charAt(level) - 'a'];
           
        }
        temp.isLeaf = true;
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode temp = root;
        int length = word.length();
       
        for(int level = 0 ; level < length ; level++ ){
            if(temp.children[word.charAt(level) - 'a'] != null){
                temp = temp.children[word.charAt(level) - 'a'];
            }
            else{
                return false;
            }
        }
        if(temp != null && temp.isLeaf == true){
            return true;
        }
        return false;
       
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode temp = root;
        int length = prefix.length();
       
        for(int level = 0 ; level < length ; level++ ){
            if(temp.children[prefix.charAt(level) - 'a'] != null){
                temp = temp.children[prefix.charAt(level) - 'a'];
            }
            else{
                return false;
            }
        }
   
        return true;
    }
}

// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");

3Sum -Leet Code Java Solutiion

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution:-

public class Solution {

    public List<List<Integer>> threeSum(int[] nums) {

        

        Arrays.sort(nums);

        

        List<List<Integer>> res = new ArrayList<List<Integer>>();

        

        Map<String , Integer> map =  new HashMap<String, Integer>();

        

        HashSet<List<Integer>> set = new HashSet<List<Integer>>();

        

        for(int i = 0 ; i < nums.length -2 ; i++){

            

            int start = i + 1 ;

            int end = nums.length - 1;

            

            while(start < end){

                

                if(nums[i] + nums[start]+ nums[end] == 0){

                    List<Integer> temp = new ArrayList<Integer>();

                    temp.add(nums[i]);

                    temp.add(nums[start]);

                    temp.add(nums[end]);

                    set.add(temp);

                    start++;

                    end--;

                }

                else{

                if(nums[i] + nums[start]+ nums[end] < 0){

                    start++;

                }

                else{

                    end--;

                }

                }

            }

        }

        res.addAll(set);

        return res;

        

    }

}

4Sum (Leet Code Java Solution)

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Solution:-

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        
        Map<String , Integer> map =  new HashMap<String, Integer>();
        
        HashSet<List<Integer>> set = new HashSet<List<Integer>>();
        
        for(int t = 0 ; t < nums.length - 3 ; t++){
            for(int i = t+1 ; i < nums.length - 2 ; i++){
            
            int start = i + 1 ;
            int end = nums.length - 1;
            
            while(start < end){
                
                if(nums[t] + nums[i] + nums[start]+ nums[end] == target){
                    List<Integer> temp = new ArrayList<Integer>();
                    temp.add(nums[t]);
                    temp.add(nums[i]);
                    temp.add(nums[start]);
                    temp.add(nums[end]);
                    set.add(temp);
                    start++;
                    end--;
                }
                else{
                if(nums[t] + nums[i] + nums[start]+ nums[end] < target){
                    start++;
                }
                else{
                    end--;
                }
                }
            }
            }
        }
        res.addAll(set);
        return res;
    }

}