LeetCode 1650. Lowest Common Ancestor of a Binary Tree III - 二叉樹（Binary Tree）系列題3

Given two nodes of a binary tree 

p

 and 

q

, return their lowest common ancestor (LCA).

Each node will have a reference to its parent node. The definition for 

Node

 is below:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}
      

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

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
      

Constraints:

• The number of nodes in the tree is in the range 

  [2, 105]

  .

• -109 <= Node.val <= 109

• All 

  Node.val

   are unique.

• p != q

• p

   and 

  q

   exist in the tree.

這題還是236. Lowest Common Ancestor of a Binary Tree 的拓展，不同的是這題隻給定兩個節點p和q并沒有給定二叉樹的根節點，但是節點類多了一個指針指向節點在樹中的父節點（根節點的父節點為空）。

既然沒有給定樹的根節點，那自然是順着p和q的父節點路徑一路往上尋找，我們知道它們在父節點路徑上交叉相遇的那個節點就是最低公共祖先LCA節點。仔細一看其實這題跟"160. Intersection of Two Linked Lists"，一模一樣，兩條父節點路徑相當于兩個連結清單。有以下兩種解法：

解法1：把第一個節點的父節點路徑上的所有父節點放入一個集合set中，然後再周遊第二個節點的所有父節點，每遇到一個節點都判斷是否存在集合中，隻要碰到一個父節點在集合中就可以停止，該節點就是LCA節點。

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        parents = set()
        
        while p:
            parents.add(p)
            p = p.parent
        
        while q:
            if q in parents:
                return q
            q = q.parent
        
        return None
           

解法2：本題還可以使用連結清單中常用到的雙指針(Two Pointers)法，進而不用集合set把空間複雜度優化到O(1)。定義兩個指針分别指向節點p和q（如果看成兩個連結清單的話，那麼p和q就為連結清單頭，根節點就為連結清單尾），同步沿着各自父節點往上移動，當一個指針為空（根節點的父節點為空節點）停止，這時先指向空的為短路徑，還沒指到空的為長路徑；然後把一個指針重新指向長路徑的頭節點(p或q），另一個指針保持原位置不變，重新同步往上移動；當一個指針指向空時，另一個指針所在的位置到根節點的長度将與短路徑的長度一樣；這時把一個指針指向短路徑的頭，再次重新同步往上移動，當兩個指針第一次同時指向同一個節點時，該節點就是LCA節點。

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        node1, node2 = p, q
        
        while node1 and node2:
            node1 = node1.parent
            node2 = node2.parent
        
        if not node1:
            node1 = q
            while node2:
                node1 = node1.parent
                node2 = node2.parent
            node2 = p
        elif not node2:
            node2 = p
            while node1:
                node1 = node1.parent
                node2 = node2.parent
            node1 = q
        
        while node1 and node2:
            if node1 == node2:
                return node1
            node1 = node1.parent
            node2 = node2.parent
        
        return None