LeetCode 双刀流： 236. Lowest Common Ancestor of a Binary Tree

236. Lowest Common Ancestor of a Binary Tree

今天一样想继续深入讨论关於「递回（Recursion）」的议题，递回很常搭配链结串列或是树的资料结构一起使用。所以，我们也挑选了一题在树结构中适合用递回的题目来玩玩看。

先看一下题目描述

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 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3

• Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5

这个题目要找的是二元树中两个节点的「Lowest Common Ancestor（最低共同祖先）」，也就是要找出两个点的共同上层。

开始实作

在理解完题目与条件之後，那我们下一步就开始「#初探直觉解」并且一起尝试「#刻意优化」的过程：

方法 ①：递回法

根据「Lowest Common Ancestor（最低共同祖先）」的定义，我们可以稍微整理出以下规则：

• 当这两个节点处於不同的左右子树中时，那麽最低公共祖先节点就是这两棵左右子树的根节点
• 当这两个节点处於同一子树中，那麽最低公共祖先节点就是这两个节点中最低的那个节点

第一种解法直接将此规则转换成递回的形式。

用 Python 实作一次

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root

        return left if left else right

也可以用 JavaScript 复刻一次

const lowestCommonAncestor = (root, p, q) => {
  if (!root || root == p || root == q) {
    return root
  }
  const left = lowestCommonAncestor(root.left, p, q)
  const right = lowestCommonAncestor(root.right, p, q)

  if (left && right) {
    return root
  }
  return left ? left : right
}

方法 ②：Stack

第二种逻辑是用回圈的方式进行迭代，采用中序遍历的方式将经历过的点暂存到一个 Stack 中。直到找到指定的点（p 或 q）时，再将 Stack 中的往回弹出，Stack 中的每一个点都代表路径（也代表该点的祖先）。所以，我们就可以从 Stack 当中找出 p 跟 q 的 LCS。

用 Python 实作一次

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

        visited = None
        stack = []
        while stack or root:
            if root:
                stack.append(root);
                root = root.left;
            else:
                mid = stack[len(stack)-1];
                if mid.right and mid.right != visited:
                    root = mid.right
                else:
                    stack.pop()
                    visited = mid;

                    if p == q: return p
                    if mid == p: p = stack[len(stack)-1]
                    if mid == q: q = stack[len(stack)-1]
                    root = None
             

也可以用 JavaScript 复刻一次

var lowestCommonAncestor = function(root, p, q) {
    let visited = null;
    let stack = [];
    while (stack.length != 0 || root) {
      if (root) {
        stack.push(root);
        root = root.left;
      } else {
        let mid = stack[stack.length-1];
        if (mid.right && mid.right != visited) {
          root = mid.right;
        } else {
          stack.pop();
          visited = mid;

          if (p == q) return p;
          if (mid == p) p = stack[stack.length-1];
          if (mid == q) q = stack[stack.length-1];
          root = null;
        }
      }
    }
};

方法 ③：Set

第三种方法是我们可以分成两个回圈，第一个先找出其中一点的所有祖先，然後第二个回圈去判断是否有跟第一个点收集到的祖先重复。但是因为要找出最低的，所以必须将点存在 stack 中由下往上找。

用 Python 实作一次

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':


        # 先找第一个点的路径
        stack = [root]
        visited = set()
        a_ancestors = set()
        idx = 0
        while stack:
            cur=stack.pop()
            if not cur in visited:
                visited.add(cur);
                if cur.right: stack.append(cur.right)
                stack.append(cur);
                if cur.left: stack.append(cur.left);
            else:
                if cur == p or cur ==q:
                    idx = idx + 1
                if idx == 1:
                    a_ancestors.add(cur)
                if idx == 2:
                    a_ancestors.add(cur)
                    break
        
        # 再第一个点的路径是否重叠
        stack = [root];
        visited = set()
        while stack:
            cur = stack.pop()
            if not cur in visited:
                visited.add(cur)
                if cur.right: stack.append(cur.right)
                if cur.left: stack.append(cur.left)
                stack.append(cur)
            elif cur in a_ancestors:
                return cur

        return None 

也可以用 JavaScript 复刻一次

var lowestCommonAncestor = function(root, p, q) {
    // 先找第一个点的路径
    let stack = [root];
    let visited = new Set();
    let a_ancestors = new Set();
    let idx=0;
    while(stack.length){
        let cur=stack.pop();
        if(!visited.has(cur)){
            visited.add(cur);
            if(cur.right) stack.push(cur.right)
            stack.push(cur);
            if(cur.left) stack.push(cur.left);
        }else{
            if(cur===p||cur===q){
                idx++;
            }
            if(idx===1){
                a_ancestors.add(cur);
            }
            if(idx===2){
                a_ancestors.add(cur);
                break;
            }
        }
    }
    
    // 再第一个点的路径是否重叠
    stack = [root];
    visited = new Set();
    while(stack.length){
        let cur=stack.pop();
        if(!visited.has(cur)){
            visited.add(cur);
            if(cur.right) stack.push(cur.right)
            if(cur.left) stack.push(cur.left);
            stack.push(cur);
        }else{
            if(a_ancestors.has(cur)) return cur;
        }
    }
    return null;
};

反思沉淀

这个题目透过三种不同的方法解决树结构中问题，你应该会发现以前习惯的回圈迭代到了这题变得很陌生，反而递回好像比较好理解对吗？这题主要想要让大家感受到「递回」与「迭代」在某些问题上的思考差异，有时候递回其实也很好用的的。

举一反三看看相似题

最後可以从题目提供的相似题看一下有哪些类似的题目，适合作为你下一个尝试的练习：

• 235. Lowest Common Ancestor of a Binary Search Tree

嗨，大家好！我是维元，一名擅长网站开发与资料科学的双栖工程师，斜杠於程序社群【JSDC】核心成员及【资料科学家的工作日常】粉专经营。目前在 ALPHACamp 担任资料工程师，同时也在中华电信、工研院与多所学校等单位持续开课。拥有多次大型技术会议讲者与竞赛获奖经验，持续在不同的平台发表对 #资料科学、 #网页开发 或 #软件职涯 相关的分享，邀请你加入 订阅 接收最新资讯。