Google – Reset Invalid Node

Google – Reset Invalid Node
有个tree, 每个node有getId(), setId(), 还有一个Iterator来表示children。Node里面id为null或者负数都是invalid node，且id不能重复，要求找出所有Invalid node并且重新赋值

[Solution]
[Solution #1]
找max，从max + 1开始重新赋值。
cons: 会Overflow.
[Solution #2]
用HashSet找first missing number
因为每次碰到一个invalid node，都会去搜索下一个first missing number，所以时间复杂度应该还是O(n)吧。不知道对不对，感觉怪怪的，可是又想不出什么会导致n^2的case。

class Solution {   int val = 0;   public void resetInvalidNode(TNode root) {     if (root == null) {       return;     }       Set<Integer> set = new HashSet<>();     dfs(root, set);       reset(root, set);   }     private void dfs(TNode root, Set<Integer> set) {     if (root != null && root.val >= 0) {       set.add(root.val);     }       Iterator<TNode> it = root.iterator;     while (it.hasNext()) {       dfs(it.next(), set);     }   }     private void reset(TNode root, Set<Integer> set) {     if (root.val < 0 && root.val == null) {//???       while (set.contains(this.val)) {         this.val++;       }       root.val = val;     }       Iterator<TNode> it = root.iterator;     while (it.hasNext()) {       dfs(it.next(), set, this.val);     }   } }

Read full article from Google – Reset Invalid Node