[LeetCode 236. Lowest Common Ancestor of a Binary Tree(Medium)] JavaScript Recursive Solution

LeetCode 236. Lowest Common Ancestor of a Binary Tree (Medium)

題目：

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

理解：

• Input 為一個 binary tree 和 2 個 node
• 要找到最接近 2 個 node 的共同根源 node，可以是自己

First Submission (Implemented by myself)

虛擬碼：

• Traverse the tree from the root to find the two given nodes. Start from the left side of the tree, then the right side of it.
• If the current node === p or q, return the current node and assign it to the left or right variable
• If both left and right exist, return the current node. If only left/right exists, return left/right node.

實作：

結果：

Success

Runtime: 80 ms (faster than 97.85% of javascript submissions)

Memory Usage: 48.8 MB (less than 20.15% of javascript submissions)

Second Submission (After watching the official solution: Approach 1: Recursive Approach)

實作：

結果：

Fail, 14 / 31 test cases passed.

Third Submission (Debugging the second one)

發現在前一個解中，如果 root 不等於 p 或 q 的話就會是 undefined，導致在 mid + left + right 強制轉型運算後會是 NaN，所以即使 left 和 right 都是 ture，也無法執行 result = root，導致 output 是 null。

實作：

結果：

Success

Runtime: 84 ms (faster than 94.22% of javascript submissions)

Memory Usage: 48.1 MB (less than 78.94% of javascript submissions)