68 - II. 二叉树的最近公共祖先

https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/

Java

/*
 * @Author: Goog Tech
 * @Date: 2020-09-27 17:32:00
 * @LastEditTime: 2020-09-27 17:34:05
 * @Description: https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
 * @FilePath: \leetcode-googtech\剑指 Offer\#68 - II. 二叉树的最近公共祖先\Solution.java
 * @WebSite: https://algorithm.show/
 */

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    // 递归解法 😵
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 若当前节点为空或等于 q 或 p,则直接返回 root
        if(root == null || root.val == p.val || root.val == q.val) return root;
        // 递归左右子树节点
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 若 left 和 right 都为空,则说明 q 与 p 分别在 root 的异侧,因此 root 为最近公共节点
        // 反之都为空则说明 root 的左右子树都不包含 q 与 p,进而返回 null 即可
        if(left != null && right != null) return root;
        // 若 left 为空而 right 不为空,则说明 p 与 q 都不在 root 的左子树中,直接返回 right 即可
        return left == null ? right : left;
    }
}

Python

'''
Author: Goog Tech
Date: 2020-09-27 17:32:11
LastEditTime: 2020-09-27 17:33:49
Description: https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
FilePath: \leetcode-googtech\剑指 Offer\#68 - II. 二叉树的最近公共祖先\Solution.py
WebSite: https://algorithm.show/
'''

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

class Solution(object):
    # 递归解法 😵
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if not root or root.val == p.val or root.val == q.val: return root;
        left = self.lowestCommonAncestor(root.left, q, p)
        right = self.lowestCommonAncestor(root.right, q, p)
        if left and right: return root
        return right if left is None else left