2458. Height of Binary Tree After Subtree Removal Queries

initial thought, too slow

T: O(n * q), queries times
S: O(q)

/**
 * 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 int[] treeQueries(TreeNode root, int[] queries) {
        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            result[i] = calHeight(root, queries[i]) - 1;
        }
        return result;
    }
    private int calHeight(TreeNode node, int remove) {
        if (node == null) {
            return 0;
        }
        int left = 0;
        int right = 0;
        if (node.val != remove) {
            left = calHeight(node.left, remove);
            right = calHeight(node.right, remove);
        } else {
            return 0;
        }
        return Math.max(left, right) + 1;
    }
}

/**
remove 
cal height again

 */

so we need cache!! and other way to do it

T: O(n + q), querie times
S: O(n)

class Solution {

    public int[] treeQueries(TreeNode root, int[] queries) {
        Map<Integer, Integer> heightMap = new HashMap<>();
        Map<Integer, Integer> resultMap = new HashMap<>();
        dfs(root, heightMap, resultMap, 0, 0);

        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            result[i] = resultMap.get(queries[i]);
        }
        return result;
    }
    private int getNodeHeight(TreeNode node, Map<Integer, Integer> heightMap) {
        if (node == null) {
            return -1;
        }
        if (heightMap.containsKey(node.val)) {
            return heightMap.get(node.val);
        }
        int height = 1 + Math.max(getNodeHeight(node.left, heightMap), getNodeHeight(node.right, heightMap));
        heightMap.put(node.val, height);
        return height;
    }
    private void dfs(TreeNode node, Map<Integer, Integer> heightMap, Map<Integer, Integer> resultMap, int depth, int max) {
        if (node == null) {
            return;
        }
        resultMap.put(node.val, max);
        int nextDepth = depth+1;
        int leftHeight = getNodeHeight(node.left, heightMap);
        int rightHeight = getNodeHeight(node.right, heightMap);

        dfs(node.left, heightMap, resultMap, nextDepth, Math.max(max, nextDepth + rightHeight));
        dfs(node.right, heightMap, resultMap, nextDepth, Math.max(max, nextDepth + leftHeight));
    }
}

/**
idea is we get each node's height first

then cal each remove node's max height
how to cal this?

  1
 2. 3
4 5.  6

for example 

if we remove node 2, then the ans should the cur depth + the hight of same level right subtree (3 and 6)

  1 -> node
 2.  dfs(node.left 2...) 
4 5.  

3
  6
height(node.right... 3) = 1
-> max = Math.max(max, depth(1) + the hight of same level right subtree (3 and 6) (height is 1)
= Math.max(0, 1 + 1) = 2

why need max???

ex:

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

for removing 4

cal the cur_depth + rightSubtree (-1) = 2 + -1 = 1 -> 

 2
/
4

cur_depth + height(2's right, it's null so -1)
= 2 + -1 = 1
rightSubtree is null, so no more height can add to depth(1, which is in node 2 aspect) 反而變小了！

but actually ans is 3 (from right side max = 3)
so we need maxVal for the later ans!


T: O(n + q), querie times
S: O(n)
 */