[Golang][Leetcode][BinaryTree]刷題系列-236-Lowest Common Ancestor of a Binary Tree

236. Lowest Common Ancestor of a Binary Tree
Level : Medium
原題連結 : Click
題目 :
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).”
Example :
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Example 3:
Input: root = [1,2], p = 1, q = 2 Output: 1
解題思路 :
這題需要我們找出兩nodes的最低共同祖先
以下提供兩個解題思路:
第一種(我最一開始想到的): 先做一次preorder並將整棵樹存進stack,在從頭部開始找 p or q 其中一個node,若先找到 p 我就設定target為 q,反之則設target為 p ,並擷取頭部到 p(or q)的slice做為新的stack,這樣做的目的是因為preorder的關係,p 跟 q 的共同祖先們都在此新的stack中,於是我們再把此stack裡的node從尾部一個一個push出來(因為越尾部越接近當初找到的 p(or q)),並以他們為root做preorder找出是否是target的祖先,第一個符合此條件的node便是 p, q的最低共同祖先
第二種‵: 是直接將樹分成兩半做判斷,寫法也很直觀,若找到 p 或 q 就直接回傳該node,若是沒找到就回傳nil,分成兩邊就可以做篩檢,若回傳為nil就直接忽略了,往有找到的那邊繼續往下找,直到兩邊都有找到,那代表該node便是他們的最低共同祖先
Recursive-1解法
- time complexity: O(n^2) , space complexity: O(n)
Runtime: 4 ms, faster than 99.71% of Go online submissions for Lowest Common Ancestor of a Binary Tree.
|
|
Recursive-2解法
- time complexity: O(n) , space complexity: O(1)
|
|
最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!