671 Second Minimum Node In a Binary Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int min1;
    int ans = Integer.MAX_VALUE;
    public int findSecondMinimumValue(TreeNode root) {
        min1 = root.val;
        dfs(root);
        return ans < Integer.MAX_VALUE ? ans : -1;
    }

    private void dfs(TreeNode root){
        if (root != null){
            if (root.val > min1 && root.val < ans){
                ans = root.val;
            }
            else if (root.val == min1){
                dfs(root.left);
                dfs(root.right);
            }
        }
    }
}

652 Find Duplicate Subtrees

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<TreeNode> ans;
    Map<String, Integer> hash;
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        hash = new HashMap<>();
        ans = new ArrayList<>();
        dfs(root);

        return ans;
    }

    private String dfs(TreeNode root){
        if (root == null) return "#";

        String cur = root.val + "," + dfs(root.left) + "," + dfs(root.right);

        if (!hash.containsKey(cur)){
            hash.put(cur, 1);
        }
        else{
            hash.put(cur, hash.get(cur) + 1);
        }

        if (hash.get(cur) == 2) ans.add(root);

        return cur;
    }
}

572 Subtree of Another Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        return s != null && (match(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t));
    }

    private boolean match(TreeNode s, TreeNode t){
        if (s == null && t == null){
            return true;
        }
        else if (s == null || t == null){
            return false;
        }
        else{
            return s.val == t.val && match(s.left, t.left) && match(s.right, t.right);
        }
    }
}

501 Find Mode in Binary Search Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Integer prev = null;
    int max = 0, count = 1;
    public int[] findMode(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        dfs(root, list);
        int[] ans = new int[list.size()];
        for (int i = 0; i < list.size(); i++){
            ans[i] = list.get(i);
        }

        return ans;
    }

    private void dfs(TreeNode root, List<Integer> list){

        if (root == null) return;

        dfs(root.left, list);

        if (prev != null){
            if (root.val == prev){
                count++;
            }
            else{
                count = 1;
            }
        }

        if (count > max){
            max = count;
            list.clear();
            list.add(root.val);
        }
        else if (count == max){
            list.add(root.val);
        }
        prev = root.val;

        dfs(root.right, list);
    }
}

449 Serialize and Deserialize BST

297 Serialize and Deserialize Binary Tree

public class Codec {
    private static final String spliter = ",";
    private static final String NN = "X";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        buildString(root, sb);
        return sb.toString();
    }

    private void buildString(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(NN).append(spliter);
        } else {
            sb.append(node.val).append(spliter);
            buildString(node.left, sb);
            buildString(node.right,sb);
        }
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Deque<String> nodes = new LinkedList<>();
        nodes.addAll(Arrays.asList(data.split(spliter)));
        return buildTree(nodes);
    }

    private TreeNode buildTree(Deque<String> nodes) {
        String val = nodes.remove();
        if (val.equals(NN)) return null;
        else {
            TreeNode node = new TreeNode(Integer.valueOf(val));
            node.left = buildTree(nodes);
            node.right = buildTree(nodes);
            return node;
        }
    }
}

450 Delete Node in a BST

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;

        if (root.val < key){
            root.right = deleteNode(root.right, key);
        }
        else if (root.val > key){
            root.left = deleteNode(root.left, key);
        }
        else{
            if (root.left == null){
                return root.right;
            }
            else if (root.right == null){
                return root.left;
            }

            TreeNode minNode = findMin(root.right);
            root.val = minNode.val;
            root.right = deleteNode(root.right, root.val);

        }

        return root;
    }

    private TreeNode findMin(TreeNode root){
        while (root.left != null){
            root = root.left;
        }

        return root;
    }
}