【数据结构与算法】【LeetCode】【二叉树】236.二叉树的最近公共祖先

fishni

数据结构与算法

发布于：2020年11月23日

二叉树创建，最近公共祖先

题目

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

最近公共祖先的定义为：“对于有根树 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 为不同节点且均存在于给定的二叉树中。

题解

最近公共祖先的定义：

设节点 root为节点 p, q的某公共祖先，若其左子节点 root.left 和右子节点 root.right都不是 p,q的公共祖先，则称 root 是 “最近的公共祖先” 。

根据以上定义，若 rootroot 是 p, qp,q 的最近公共祖先，则只可能为以下情况之一：
1. p 和 q 在 root 的子树中，且分列root 的异侧（即分别在左、右子树中）；
2. p = root ，且q 在 root 的左或右子树中；
3. q = root ，且 p 在 root的左或右子树中；

考虑通过递归对二叉树进行后序遍历，当遇到节点 p 或 q 时返回。从底至顶回溯，当节点 p, q在节点 root的异侧时，节点root 即为最近公共祖先，则向上返回 root 。

递归解析：
1. 终止条件：
  - 当越过叶节点，则直接返回 null ；
  - 当 root 等于 p,q，则直接返回 root；
2. 递推工作：
  - 开启递归左子节点，返回值记为 left ；
  - 开启递归右子节点，返回值记为 right ；
3. 返回值：根据 left和 right ，可展开为四种情况；
  - 1.当 left 和 right 同时为空：说明root 的左 / 右子树中都不包含 p,q ，返回null ；
  - 2.当 left和 right 同时不为空：说明 p, q分列在 root 的异侧（分别在左 / 右子树），因此 root 为最近公共祖先，返回 root ；
  - 3.当 left 为空，right 不为空：p,q 都不在 root 的左子树中，直接返回 right 。具体可分为两种情况：
    - p,q 其中一个在root 的右子树中，此时right 指向 p（假设为p ）；
    - p,q 两节点都在 root 的右子树中，此时的right 指向最近公共祖先节点；
  - 4.当 left 不为空，right 为空：与情况 3. 同理；
    
    观察发现，情况 1. 可合并至 3. 和 4. 内，详见文章末尾代码。

# Definition for a binary tree node.
from queue import Queue

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
def create_tree(list_tree,p,q):
    if  not list_tree:
        return None
    new_queue= Queue()
    root = TreeNode(list_tree[0])
    new_queue.put(root) # 先入队一个结点
    count = 1
    while not new_queue.empty() and count<len(list_tree):
        dequeue = new_queue.get() # 出队
        # 返回p,q指向结点
        if p==dequeue.val:
            p=dequeue
        if q==dequeue.val:
            q=dequeue
            
        if not dequeue.left and  not dequeue.right:
            if count<len(list_tree) and list_tree[count]:
                dequeue.left=TreeNode(list_tree[count])
            count= count+1
            if count<len(list_tree) and list_tree[count]:
                dequeue.right=TreeNode(list_tree[count])
            count= count+1

            if dequeue.left:
                new_queue.put(dequeue.left)
            if dequeue.right:
                new_queue.put(dequeue.right)
    #print(p.val,q.val)
    return root,p,q
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 not left: return right
        if not right: return left
        return root

root = [3,5,1,6,2,0,8,None,None,7,4]
p=5
q=1
root_tree,p,q=create_tree(root,p,q)
a=Solution()
result =a.lowestCommonAncestor(root_tree,p,q)
result.val