Given a binary tree, find if there are two subtrees that are the same. (i.e. the tree structures are the same; the values on all corresponding nodes are the same). You should find the largest subtree and don’t use brute force.
public class Solution {
private class SubtreeTuple{
// size of tree, negative value to reprensent invalid BST
int size;
// subtree min / max value
int min;
int max;
public SubtreeTuple(int size, int min, int max){
this.size = size;
this.min = min;
this.max = max;
}
}
public int largestBSTSubtree(TreeNode root) {
return Math.abs(helper(root).size);
}
private SubtreeTuple helper(TreeNode root){
if(root == null) return new SubtreeTuple(0, Integer.MAX_VALUE, Integer.MIN_VALUE);
SubtreeTuple left = helper(root.left);
SubtreeTuple right = helper(root.right);
if(left.size < 0 || root.val <= left.max || right.size < 0 || root.val >= right.min){
return new SubtreeTuple(Math.max(Math.abs(left.size), Math.abs(right.size)) * -1,
Math.min(left.min, root.val), Math.max(right.max, root.val));
} else {
// current left + right + root is a valid BST
return new SubtreeTuple(left.size + right.size + 1,
Math.min(root.val, left.min),
Math.max(root.val, right.max));
}
}
}
public class Solution {
private class Tuple{
// ABS : max count
// Sign: +/- , is/not univalue subtree
//
int count;
Integer val;
public Tuple(int count, Integer val){
this.count = count;
this.val = val;
}
}
public int countUnivalSubtrees(TreeNode root) {
return Math.abs(helper(root).count);
}
private Tuple helper(TreeNode root){
if(root == null) return new Tuple(0, null);
Tuple left = helper(root.left);
Tuple right = helper(root.right);
if(left.count < 0 || right.count < 0 ||
(left.val != null && !left.val.equals(root.val)) ||
(right.val != null && !right.val.equals(root.val))){
return new Tuple((Math.abs(left.count) + Math.abs(right.count)) * -1, 0);
} else {
return new Tuple(left.count + right.count + 1, root.val);
}
}
}
public class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
if(root.left == null && root.right == null) return 1;
int leftPath = 0;
int rightPath = 0;
TreeNode cur = root;
while(cur != null){
leftPath ++;
cur = cur.left;
}
cur = root;
while(cur != null){
rightPath ++;
cur = cur.right;
}
if(leftPath == rightPath) return (2 << (leftPath - 1)) - 1;
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
public class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int l = leftHeight(root.left);
int r = leftHeight(root.right);
if (l == r) { // left side is full
return countNodes(root.right) + (1<<l);
}
return countNodes(root.left) + (1<<r);
}
private int leftHeight(TreeNode node) {
int h = 0;
while (node != null) {
h++;
node = node.left;
}
return h;
}
}
public class Solution {
private static class TreeNode{
int val;
TreeNode left, right;
public TreeNode(int val){
this.val = val;
}
}
private static class TreeTuple{
String key;
int id;
int size;
public TreeTuple(String key, int id, int size){
this.key = key;
this.id = id;
this.size = size;
}
}
public static int largestSubtree(TreeNode root){
HashMap<String, Integer> keyMap = new HashMap<>();
HashMap<Integer, List<TreeTuple>> groupMap = new HashMap<>();
int[] id = new int[1];
id[0] = 1;
postOrder(root, keyMap, groupMap, id);
Iterator<Integer> iter = groupMap.keySet().iterator();
int maxSize = 0;
while(iter.hasNext()){
int groupId = iter.next();
List<TreeTuple> list = groupMap.get(groupId);
if(list.size() > 1) maxSize = Math.max(maxSize, list.get(0).size);
}
return maxSize;
}
// keyMap : Key - String - (val, leftId, rightId)
// Val - Integer - groupId
// groupMap : Key - Integer - groupId
// Val - Integer - number of occurrances
private static TreeTuple postOrder(TreeNode root, HashMap<String, Integer> keyMap,
HashMap<Integer, List<TreeTuple>> groupMap, int[] id){
if(root == null) return new TreeTuple("0,0,0", 0, 0);
TreeTuple left = postOrder(root.left, keyMap, groupMap, id);
TreeTuple right = postOrder(root.right, keyMap, groupMap, id);
int curId;
TreeTuple curTuple;
String key = "" + root.val + "," + left.id + "," + right.id;
if(!keyMap.containsKey(key)){
curId = id[0]++;
keyMap.put(key, curId);
groupMap.put(curId, new ArrayList<>());
curTuple = new TreeTuple(key, curId, left.size + right.size + 1);
groupMap.get(curId).add(curTuple);
} else {
curId = keyMap.get(key);
curTuple = new TreeTuple(key, curId, left.size + right.size + 1);
groupMap.get(curId).add(curTuple);
}
return curTuple;
}
public static void main(String[] args) {
/*
TreeNode root = new TreeNode(5);
TreeNode root2 = new TreeNode(9);
TreeNode root3 = new TreeNode(2);
TreeNode root4 = new TreeNode(7);
TreeNode root5 = new TreeNode(3);
TreeNode root6 = new TreeNode(12);
TreeNode root7 = new TreeNode(10);
TreeNode root8 = new TreeNode(9);
TreeNode root9 = new TreeNode(2);
TreeNode root10 = new TreeNode(7);
TreeNode root11 = new TreeNode(3);
root.left = root2;
root.right = root6;
root2.left = root3;
root2.right = root4;
root4.left = root5;
root6.left = root7;
root6.right = root8;
root8.left = root9;
root8.right = root10;
root10.left = root11;
*/
TreeNode root = new TreeNode(0);
TreeNode rootl2 = new TreeNode(1);
TreeNode rootr3 = new TreeNode(1);
TreeNode rootl4 = new TreeNode(2);
TreeNode rootr5 = new TreeNode(2);
TreeNode rootl6 = new TreeNode(3);
TreeNode rootr7 = new TreeNode(3);
TreeNode rootl8 = new TreeNode(4);
TreeNode rootr9 = new TreeNode(4);
TreeNode rootl10 = new TreeNode(5);
TreeNode rootr11 = new TreeNode(5);
TreeNode rootl12 = new TreeNode(6);
TreeNode rootr13 = new TreeNode(6);
root.left = rootl2;
root.right = rootr3;
rootl2.left = rootl4;
rootl2.right = rootl6;
rootl4.left = rootl8;
rootl4.right = rootl10;
rootl6.right = rootl12;
rootr3.left = rootr5;
rootr3.right = rootr7;
rootr5.left = rootr9;
rootr5.right = rootr11;
rootr7.right = rootr13;
System.out.println(largestSubtree(root));
}
}
