【LeetCode】235. Lowest Common Ancestor of a Binary Search Tree 解题报告（Java & Python）

作者：负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/

题目描述

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

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).”

Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]

        _______6______

       /              \

    ___2__          ___8__

   /      \        /      \

   0      _4       7       9

         /  \

         3   5

Example 1:

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

Output: 6

Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

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

Output: 2

Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself

             according to the LCA definition.

Note:

All of the nodes’ values will be unique.
p and q are different and both values will exist in the BST.

题目大意

在一个BST中，查找p和q节点的最小公共祖先。

解题方法

注意是BST，那么使用分而治之的策略，用递归来找到左边和右边的最低的公共祖先。

答案：

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class Solution {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if(root==null||p==root||q==root){

            return root;

        }

        //devide

        TreeNode left=lowestCommonAncestor(root.left,p,q);

        TreeNode right=lowestCommonAncestor(root.right,p,q);

        //conquer

        if(left!=null&&right!=null){

            return root;

        }else if(left!=null){

            return left;

        }else{

            return right;

        }

    }

}

AC:11ms

二刷，python

第一遍做这个题是两年前，现在用Python刷这个感觉特别简单。

因为BST本身的属性，所以比较节点的值和根节点的值的大小就知道下一步去哪里查找了。很简单，看代码。

递归版本：

# 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 min(p.val, q.val) <= root.val and max(p.val, q.val) >= root.val:

            return root

        elif p.val < root.val and q.val < root.val:

            return self.lowestCommonAncestor(root.left, p, q)

        elif p.val > root.val and q.val > root.val:

            return self.lowestCommonAncestor(root.right, p, q)

循环版本：

# 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

        """

        while root:

            if p.val < root.val and q.val < root.val:

                root = root.left

            elif p.val > root.val and q.val > root.val:

                root = root.right

            else:

                break

        return root

这个题是236. Lowest Common Ancestor of a Binary Tree的特例，所以可以直接使用236的代码就能通过。

# 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 == 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

日期

2016/5/1 14:05:25
2018 年 6 月 22 日 ———— 这周的糟心事终于完了
2018 年 11 月 19 日 —— 周一又开始了

巴特西

【LeetCode】235. Lowest Common Ancestor of a Binary Search Tree 解题报告（Java & Python）

目录

题目描述

题目大意

解题方法

日期

最新文章

热门文章