Google – Sum of Subtree with Only Parent Pointer

Google – Sum of Subtree with Only Parent Pointer
给一个list of nodes, 每个node只有val和parent pointer。再给其中的一个node t, 要求返回sum of subtree of t

[Solution]
其实就是用hash table重新建tree就好了。
下面的code是重新建tree之后返回整个tree的sum，忘了再输入一个node了，但是思路应该都一样，建完dfs。

  public int subTreeSum(List<TNode> nodes, TNode node) {

    if (nodes == null || nodes.isEmpty() || node == null) {

      return 0;

    }

     

    Map<TNode, List<TNode>> tree = new HashMap<>();

    for (TNode t : nodes) {

      tree.putIfAbsent(t.parent, new ArrayList<>());

      tree.get(t.parent).add(t);

    }

     

    return dfs(node, tree);

  }

   

  private int dfs(TNode node, Map<TNode, List<TNode>> tree) {

    if (node == null) {

      return 0;

    }

     

    int sub = 0;

    for (TNode child : tree.get(node)) {

      sub += dfs(child, tree);

    }

     

    return sub + node.val;

  }

Read full article from Google – Sum of Subtree with Only Parent Pointer