235. Lowest Common Ancestor of a Binary Search Tree(Tree-Easy)

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 v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

题目:求二叉树的LCA,也就是两个节点的最低公共祖先。比如上图的二叉树,节点2和8的LCA是6,节点2和4的LCA是2。

思路:观察给定的二叉树可知,二叉树中任何节点:左节点的值 < 根节点的值 < 右节点的值。根据这个性质,可以做出如下判断:

  • 如果p、q都比根节点小,则在左子树中递归查找最低公共祖先节点。
  • 如果p、q都比根节点大,则在右子树中递归查找最低公共祖先节点。
  • 如果p、q一个比根节点大,一个比根节点小,或者有一个等于根节点,则根节点即为最低公共祖先节点。

Language : cpp

递归方法:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (p->val < root->val && root->val > q->val)
            return lowestCommonAncestor(root->left, p, q);
        else if (p->val > root->val && root->val < q->val)
            return lowestCommonAncestor(root->right, p, q);
        else
            return root;
    }
};

Language : python

递归方法:

# 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 p.val < root.val > q.val:
            return self.lowestCommonAncestor(root.left, p, q)
        elif p.val > root.val < q.val:
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root

迭代方法:

# 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 True:
            if p.val < root.val > q.val:
                root = root.left
            elif p.val > root.val < q.val:
                root = root.right
            else:
                return root

代码获取: https://github.com/Jack-Cherish/LeetCode

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏书山有路勤为径

二叉树-路径之和

给定一个二叉树与整数sum,找出所有从根节点到叶结点的路径,这些路径上的节点值累加和为sum。

8420
来自专栏用户画像

剑指offer 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

8630
来自专栏desperate633

LeetCode 94. Binary Tree Inorder Traversal题目代码

6530
来自专栏desperate633

LintCode 将二叉树拆成链表题目分析代码

将一棵二叉树按照前序遍历拆解成为一个假链表。所谓的假链表是说,用二叉树的 right 指针,来表示链表中的 next 指针。

7530
来自专栏和蔼的张星的图像处理专栏

85. 在二叉查找树中插入节点常规操作

You can assume there is no duplicate values in this tree + node.

24120
来自专栏计算机视觉与深度学习基础

Leetcode 124 Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum. For this problem, a path is de...

22190
来自专栏二进制文集

LeetCode 二叉树 题目分类汇总

简书的 markdown 都不支持 [TOC] 语法……我就不贴目录了。下面按照类别,列出了29道关于二叉树的题目。认真看会发现,其实题目核心思想都是DFS(如...

28540
来自专栏aCloudDeveloper

LeetCode:114_Flatten Binary Tree to Linked List | 将一棵二叉树变成链表的形式 | Medium

要求:Given a binary tree, flatten it to a linked list in-place.将二叉树转化为平坦序列的树。比如: ?...

20850
来自专栏desperate633

LintCode 二叉树的锯齿形层次遍历题目分析代码

给出一棵二叉树,返回其节点值的锯齿形层次遍历(先从左往右,下一层再从右往左,层与层之间交替进行)

9730
来自专栏纯洁的微笑

平衡二叉树 AVL树结构详解 [Java实现]

https://blog.csdn.net/zhang6622056/article/details/82698859

26020

扫码关注云+社区

领取腾讯云代金券