501,Find Mode in Binary Search Tree
Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.
If the tree has more than one mode, return them in any order.
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
- The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
- Both the left and right subtrees must also be binary search trees.
Example 1:
Input: root = [1,null,2,2]
Output: [2]
Example 2:
Input: root = [0]
Output: [0]
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -105 <= Node.val <= 105
Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).
class Solution {
Map<Integer, Integer> map;
public int[] findMode(TreeNode root) {
map = new HashMap<>();
searchInBST(root);
int maxFreq = -1;
List<Integer> list = new ArrayList<>();
for (int key : map.keySet()) {
int freq = map.get(key);
if (maxFreq < freq) {
maxFreq = freq;
list.clear();
list.add(key);
continue;
}
if (maxFreq == freq) {
list.add(key);
}
}
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
res[i] = list.get(i);
}
return res;
}
private void searchInBST(TreeNode node) {
if (node == null) return;
if (map.containsKey(node.val)) {
map.put(node.val, map.get(node.val) + 1);
} else {
map.put(node.val, 1);
}
searchInBST(node.left);
searchInBST(node.right);
}
}
530.Minimum Absolute Difference in BST
Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.
Example 1:
Input: root = [4,2,6,1,3]
Output: 1
Example 2:
Input: root = [1,0,48,null,null,12,49]
Output: 1
Constraints:
- The number of nodes in the tree is in the range
[2, 104]. 0 <= Node.val <= 105
InOrder Traversal of a Binary Search Tree always Gives a sorted Array and after that just calculate the distance between the 2 adjacent number of the array.
class Solution {
ArrayList<Integer> al = new ArrayList<>();
public int getMinimumDifference(TreeNode root) {
inOrder(root);
int minDist = Integer.MAX_VALUE;
for(int i = 1 ; i < al.size(); i ++){
minDist = Math.min(minDist,al.get(i) - al.get(i-1));
}
return minDist;
}
public void inOrder(TreeNode root){
if(root == null){
return ;
}
inOrder(root.left);
al.add(root.val);
inOrder(root.right);
}
}
543,Diameter of Binary Tree
Given the root of a binary tree, return 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.
The length of a path between two nodes is represented by the number of edges between them.
Example 1:
Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].
Example 2:
Input: root = [1,2]
Output: 1
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -100 <= Node.val <= 100
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int diameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
height(root);
return diameter;
}
public int height(TreeNode root) {
if(root==null){
return 0;
}
//recursively get the height of left and right subtree
int leftHeight=height(root.left);
int rightHeight=height(root.right);
//update the diameter by comparing the current diameter with the sum of left and right subtree height
diameter=Math.max(diameter, leftHeight+rightHeight);
return Math.max(leftHeight, rightHeight)+1;
}
}
563，Binary Tree Tilt
Given the root of a binary tree, return the sum of every tree node’s tilt.
The tilt of a tree node is the absolute difference between the sum of all left subtree node values and all right subtree node values. If a node does not have a left child, then the sum of the left subtree node values is treated as 0. The rule is similar if the node does not have a right child.
Example 1:
Input: root = [1,2,3]
Output: 1
Explanation:
Tilt of node 2 : |0-0| = 0 (no children)
Tilt of node 3 : |0-0| = 0 (no children)
Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3)
Sum of every tilt : 0 + 0 + 1 = 1
Example 2:
Input: root = [4,2,9,3,5,null,7]
Output: 15
Explanation:
Tilt of node 3 : |0-0| = 0 (no children)
Tilt of node 5 : |0-0| = 0 (no children)
Tilt of node 7 : |0-0| = 0 (no children)
Tilt of node 2 : |3-5| = 2 (left subtree is just left child, so sum is 3; right subtree is just right child, so sum is 5)
Tilt of node 9 : |0-7| = 7 (no left child, so sum is 0; right subtree is just right child, so sum is 7)
Tilt of node 4 : |(3+5+2)-(9+7)| = |10-16| = 6 (left subtree values are 3, 5, and 2, which sums to 10; right subtree values are 9 and 7, which sums to 16)
Sum of every tilt : 0 + 0 + 0 + 2 + 7 + 6 = 15
Example 3:
Input: root = [21,7,14,1,1,2,2,3,3]
Output: 9
Constraints:
- The number of nodes in the tree is in the range
[0, 104]. -1000 <= Node.val <= 1000
Approach1: Brute Force(Finding Sum at every Node) Explanation: Find the sum of left subtree and right subtree using findSum function and take its absolute difference. So we will return the sum of absolute diff and leftSubtree tilt and right subtree tilt which will be your total tilt of the tree.
class Solution {
int findSum(TreeNode root){
if(root==null) return 0;
return root.val + findSum(root.left) + findSum(root.right);
}
public int findTilt(TreeNode root) {
if(root==null) return 0;
int left = findTilt(root.left);
int right = findTilt(root.right);
return Math.abs(findSum(root.left)-findSum(root.right))+left+right;
}
}
572,Subtree of Another Tree
Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.
A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself.
Example 1:
Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true
Example 2:
Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false
Constraints:
- The number of nodes in the
roottree is in the range[1, 2000]. - The number of nodes in the
subRoottree is in the range[1, 1000]. -104 <= root.val <= 104-104 <= subRoot.val <= 104
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isidentical(TreeNode root, TreeNode subRoot) {
if(root==null && subRoot==null){
return true;
}
else if(root==null || subRoot==null || root.val!=subRoot.val ){
return false ;
}
if(!isidentical(root.left,subRoot.left)){
return false;
}
if(!isidentical(root.right,subRoot.right)){
return false;
}
return true;
}
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root==null){
return false;
}
if(root.val==subRoot.val){
if(isidentical(root,subRoot)){
return true;
}}
return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);
}
}
606,Construct String from Binary Tree
Given the root of a binary tree, construct a string consisting of parenthesis and integers from a binary tree with the preorder traversal way, and return it.
Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree.
Example 1:
Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the unnecessary empty parenthesis pairs. And it will be "1(2(4))(3)"
Example 2:
Input: root = [1,2,3,null,4]
Output: "1(2()(4))(3)"
Explanation: Almost the same as the first example, except we cannot omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -1000 <= Node.val <= 1000
public String tree2str(TreeNode root) {
if(root == null) return "";
String output = String.valueOf(root.val);
if(root.left != null || root.right != null) output += "(" + tree2str(root.left) + ")";
if(root.right != null) output += "(" + tree2str(root.right) + ")";
return output;
}
617,Merge Two Binary Trees
You are given two binary trees root1 and root2.
Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.
Return the merged tree.
Note: The merging process must start from the root nodes of both trees.
Example 1:
Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]
Example 2:
Input: root1 = [1], root2 = [1,2]
Output: [2,2]
Constraints:
- The number of nodes in both trees is in the range
[0, 2000]. -104 <= Node.val <= 104
Approach1
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private TreeNode mergeNode(TreeNode root1, TreeNode root2){
if(root1 == null && root2 == null){
return null;
}else if(root1 ==null){
return root2;
}else if(root2 ==null){
return root1;
}
TreeNode newTreeNode = new TreeNode(0);
newTreeNode.val = root1.val + root2.val;
newTreeNode.left = mergeNode(root1.left,root2.left);
newTreeNode.right = mergeNode(root1.right,root2.right);
return newTreeNode;
}
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
TreeNode result = new TreeNode(0);
result = mergeNode(root1,root2);
return result;
}
}
Approach2
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null)
return t2;
if (t2 == null)
return t1;
t1.val += t2.val;
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}
}
