#62 Coding面試 LeetCode #236 Lowest Common Ancestor of a Binary Tree

原文題目在 https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree．

題目是說給你三個 TreeNode, 第一個 TreeNode 是這個樹的 root, 第二個和第三個 TreeNode 是這顆樹裡面任意兩個 TreeNode. 所以，題目都這樣說了，你就不用擔心它會給你一個不在這顆樹裡面的 TreeNode．題目問你要在任意給你樹裡面兩個 TreeNode 後，你要找出這兩個 TreeNode 最低位置的父節點．所謂最低位置是指離 root 越遠越好．

看到這題目便想到跟 TreeNode 往上走到 root 的路徑有關，因為你要找的就是從任意兩 TreeNode 出發，會在那一個 node 第一次相遇．有一個很直覺的想法是在這兩個 node 一起往上走，但問題來了，你怎麼知道往上走要走到那去呢 ? 再者，任意兩 node 一起往上走不見得會在最小高度的 ancestor node 剛好碰在一起，因為任意兩 node 的高度不見得是一樣的．我當初想這一題時，便沒有想到要讓兩個 node 一起往上走，而是先讓其中一個 node 一直往上走到 root，把經過的 node 都記錄下來，完成之後便開始另一個 node 往上走，每往上走一個 node 時便比較第一個 node 是不是有走過同樣的 node，如果有的話，就代表找到了，如果沒有的話，就繼續往上走，一直到找到為止．

因此，我們需要把整顆樹的 "路徑" 和第一個參數 TreeNode 往上走的 "路徑" 記錄下來．在這裡，比較特別的是用 Dictionary (Hash table)，而不是用 List．第二個參數的 node 只要在每一層往上走的過程中，檢查該位置的 node 是否在於第一個參數 TreeNode 的 "路徑" 就好了，其參考程式碼如下:

為何 Root 和第一個參數 TreeNode 的路徑是用 Dictionary (Hash table)，而不是用 Stack/Queue 或 List 來記錄路徑．答案在以前的文章已經說明過了，這點就留給讀者想一想．