1676. Lowest Common Ancestor of a Binary Tree IV

Solution idea

LCA

• input nodes 一定存在于tree中

• 逻辑与LCA I: 236. Lowest Common Ancestor of a Binary Tree一致

• 因为input nodes 是一个array，所以使用一个 HashMap 来当作input nodes的set

  • Base case comparison: LCA I vs. LCA IV
  • if root == p || root == q {return root} vs. if set[root] == true {return root}

Time complexity = $O(h)$, Space complexity = $O(n)$ where $n$ is number of input nodes