[236][中等][DFS] 二叉搜索树的最近公共祖先

题目描述

236. 二叉树的最近公共祖先 剑指 Offer 68 - II. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:

• 所有节点的值都是唯一的。

• p、q 为不同节点且均存在于给定的二叉树中。

解题思路

由上向下的思路

在DFS递归的过程中, 判断以当前结点为根节点的树中都有哪些节点, 找到第一个包含p和q的节点, 就是要找的最近公共祖先节点.

使用哈希表存储每个节点代表的树中包含的所有节点.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def dfs(node):
            if node is None:
                return False, set(), None

            node_set = set([node])
            left_status, left_set, parnet = dfs(node.left)
            if left_status:
                return left_status, left_set, parnet
            node_set = node_set.union(left_set)
            if p in node_set and q in node_set:
                return True, node_set, node
            right_status, right_set, parnet = dfs(node.right)
            if right_status:
                return right_status, right_set, parnet
            node_set = node_set.union(right_set)
            if p in node_set and q in node_set:
                return True, node_set, node
            return False, node_set, None

        _, _, p = dfs(root)

        return p

由下向上的思路

236. 二叉树的最近公共祖先（后序遍历 DFS ，清晰图解） 【C++ 经典递归】思路非常好理解 时间复杂度O(n), 空间复杂度O(n)

构建一个函数, 返回的内容是候选的最近公共祖先结点.

首先, 一个节点root如果是p和q的最近公共祖先, 则只可能是以下几种情况:

• p和q分别在root的左右子树中, 不能在同一侧子树中

• p = root, 且q在root的任一子树中

• q = root, 且p在root的任一子树中

因此, DFS使用的递归函数在遇到p或q时, 就无需继续向下遍历, 可以开始向上回溯了. 因为节点p或q满足上面的第二, 第三条, 如果真实情况就是q在p为根节点的子树中, 或反过来, 那么这个节点就是最近公共祖先节点.

在回溯的过程中, 根据左子树left和右子树right的返回, 有四种情况:

• left和right同时为None, 说明root的左右子树都不包含p和q, 继续向上返回None

• left和right都不为空, 说明p和q分别在root的不同侧, 因此root是最近公共祖先节点, 返回root

• left为空, right不为空, 直接返回right

  • 可能是right中只有p, 没有q(或只有q), 此时的right是指向p为根节点的

  • 可能right中包含p和q节点, 此时的right是指向最近公共祖先节点的

• left不为空, right为空, 返回left, 具体情况同第三种情况

还有一个边际情况是遇到了空节点, 直接返回None就可以.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        def dfs(node):
            if not node or node is p or node is q:
                return node

            left = dfs(node.left)
            right = dfs(node.right)
            if not left:
                return right
            if not right:
                return left
            return node
        return dfs(root)