LeetCode 235/236 LCA问题(Python)
LCA问题
LCA问题定义为,给定一个二叉树,找到树中两个指定节点的最近公共祖先。(来源于LeetCode 236)
最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大 (一个节点也可以是它自己的祖先)。”
如下图所示二叉树:
节点5和节点1的最近公共祖先的节点3,节点5和节点4的最近公共祖先是节点5。
文章图片
二叉搜索树
在解决上述问题之前,我们先提一个概念——二叉搜索树。
二叉搜索树,也称二叉查找树(Binary Search Tree),维基百科上对其定义为一棵空树或者具有以下性质的二叉树:
- 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
- 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
- 任意节点的左、右子树也分别为二叉查找树;
- 没有键值相等的节点。
如果把上述LeetCode 236中的二叉树换为二叉搜索树,便得到了二叉搜索树的LCA问题。
文章图片
简单来说,二叉搜索树是二叉树中一个特例,因此题目在给我们二叉搜索树时,我们一定要往二叉搜索树的特有性质上想。而二叉搜索树最大的特点是 必然满足其左节点< 根节点 <右节点(当然前提是这些节点存在)。
解题思路 这时,我们就可以利用这个思路来解决问题。
当给定的两节点p,q都小于根节点时,我们就可以直接到左子树里去寻找公共祖先,因为根据上述的性质,肯定和根节点、右子树都没关系了;
同理,当给定的两节点p,q都大于根节点时,我们就可以直接到右子树里去寻找公共祖先;
剩下的情况就只有p,q其一小于或等于根节点,另一大于或等于根节点,这时我们就可以直接判断该根节点是公共祖先。
递归
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root: return# p,q均小于根节点,到左子树里寻找公共祖先
if p.val < root.val and q.val < root.val:
return self.lowestCommonAncestor(root.left, p, q)# p,q均大于根节点,到右子树里寻找公共祖先
if p.val > root.val and q.val > root.val:
return self.lowestCommonAncestor(root.right, p, q)# p,q其一小于或等于根节点,另一大于或等于根节点,该根节点就是公共祖先
return root
循环
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':while root:
# p,q均大于根节点,到右子树里寻找公共祖先
if p.val > root.val and q.val > root.val:
root = root.right# p,q均小于根节点,到左子树里寻找公共祖先
elif p.val < root.val and q.val < root.val:
root = root.left# p,q其一小于或等于根节点,另一大于或等于根节点,该根节点就是公共祖先
else:
return rootreturn
二叉树的LCA问题(LeetCode 236)
让我们回到最一般的二叉树,当我们失去了二叉搜索树的特有性质时,题目的难度有所提高。
现在不能直接根据节点的值大小,选择性的进行寻找(舍弃左子树或右子树),所以我们每个节点都要考虑到。
但思路其实和上一题是一样的,都是判断节点落在左子树还是右子树,当处于一左一右时,根节点即为公共祖先。
递归
# Definition for a binary tree node.
# class TreeNode:
#def __init__(self, x):
#self.val = x
#self.left = None
#self.right = Noneclass Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or p == root or q == root:
return root# 递归判断p,q节点是在左子树还是右子树
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
【LeetCode 235/236 LCA问题(Python)】2019.8.15 修改部分表述
推荐阅读
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 默示录【二】
- 二叉树路径节点关键值和等于目标值(LeetCode--112&LeetCode--113)
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器(Swift)
- LeetCode(03)Longest|LeetCode(03)Longest Substring Without Repeating Characters
- Leetcode|Leetcode No.198打家劫舍
- [leetcode数组系列]1两数之和
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路