文档章节

236. 二叉树的最近公共祖先

o
 osc_w9s1w4o0
发布于 2019/04/01 18:42
字数 708
阅读 5
收藏 0

精选30+云产品,助力企业轻松上云!>>>

236. 二叉树的最近公共祖先

题意

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

解题思路

  1. 后序遍历法,将pq的公共父节点问题转化为找到一个节点node使得p、q分别位于node的左右子树中;

    • 若p和q要么分别位于左右子树中,那么对左右子结点调用递归函数,会分别返回p和q结点的位置,而当前结点正好就是p和q的最小共同父结点,直接返回当前结点即可。

    • 若p和q同时位于左子树,这里有两种情况,一种情况是left会返回p和q中较高的那个位置,而right会返回空,所以我们最终返回非空的left即可。还有一种情况是会返回p和q的最小父结点,就是说当前结点的左子树中的某个结点才是p和q的最小父结点,会被返回。

    • 若p和q同时位于右子树,同样这里有两种情况,一种情况是right会返回p和q中较高的那个位置,而left会返回空,所以我们最终返回非空的right即可,还有一种情况是会返回p和q的最小父结点,就是说当前结点的右子树中的某个结点才是p和q的最小父结点,会被返回。

    1. 只要找到其中的一个结点,就不会继续往下找,比如同在左子树上,也就是上面说到的第二点;

    2. 如果是分别在两边子树上,那么left和right就都能够找到,此时返回的就是他们的父亲结点,也就是上面说到的第一点;

  1. 找出两个结点的路径,对路径中的值进行比对,直到出现不一样的结点为止;

实现

# 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 not left:
           return right
       elif not right:
           return left
       return root

def lowestCommonAncestor(self, root, p, q):
       """
      比对路径
      :type root: TreeNode
      :type p: TreeNode
      :type q: TreeNode
      :rtype: TreeNode
      """
       pathP, pathQ = self.findPath(root, p), self.findPath(root, q)
       lenP, lenQ = len(pathP), len(pathQ)
       ans, x = None, 0
       # 找出出现不一致的结点,则上一个结点则为最近公共结点
       while x < min(lenP, lenQ) and pathP[x] == pathQ[x]:
           ans, x = pathP[x], x + 1
       return ans
       
   def findPath(self, root, target):
    """
    获取结点的路径
    """
       stack = []
       lastVisit = None
       while stack or root:
           if root:
               stack.append(root)
               root = root.left
           else:
               peek = stack[-1]
               if peek.right and lastVisit != peek.right:
                   root = peek.right
               else:
                   if peek == target:
                       return stack
                   lastVisit = stack.pop()
                   root = None
       return stack
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
LeetCode 面试题68 - II. 二叉树的最近公共祖先

我的LeetCode:https://leetcode-cn.com/u/ituring/ 我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii LeetCode 面试题68 - II. 二叉树的最近公共祖先 与以下题目相......

图灵的图,图灵的灵。
05/13
0
0
二叉树-最近的公共祖先

已知二叉树,求二叉树中给定的两个节点的最近公共祖先。 最近公共祖先: 两节点v与w的最近公共祖先u,满足在树上最低(离根最 远),且v,w两个节点都是u的子孙。 LeetCode 236. Lowest Common ...

徐凯_xp
2018/04/30
0
0
LeetCode 236. 二叉树的最近公共祖先

我的LeetCode:https://leetcode-cn.com/u/ituring/ 我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii LeetCode 236. 二叉树的最近公共祖先 题目 给定一个二叉树, 找......

图灵的图,图灵的灵。
05/12
0
0
236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的...

码奴生来就只知道前进
03/31
0
0
Leetcode: 236 二叉树的最近公共祖先

题目 链接:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于...

泛泛之素
05/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

聊聊rocketmq-client-go的TraceInterceptor

序 本文主要研究一下rocketmq-client-go的TraceInterceptor TraceInterceptor rocketmq-client-go-v2.0.0/producer/interceptor.go // WithTrace support rocketmq trace: https://github.c......

go4it
48分钟前
0
0
如何在Android文本视图周围添加边框? - How do I put a border around an Android textview?

问题: 是否可以在textview周围绘制边框? 解决方案: 参考一: https://stackoom.com/question/EfXR/如何在Android文本视图周围添加边框 参考二: https://oldbug.net/q/EfXR/How-do-I-put...

法国红酒甜
今天
10
0
设计模式(4) 建造者模式

什么是建造者模式 经典建造者模式的优缺点 对建造者模式的扩展 什么是建造者模式 建造者模式将一个复杂的对象的构建与它的表示分离,使得同样的构建过程可以创建不同的表示。创建者模式隐藏了...

zhixin9001
今天
14
0
ArrayList源码分析 —— JDK8

ArrayList的特性 ArrayList内部使用数据作为存储结构,ArrayList可以理解为数组的扩展对象,封装了常用的和非常用的操作数组的方法。以及当数组长度不足以保存数组时,自动扩容数组,通常Arr...

XuePeng77
今天
56
0
__slots__的用法? - Usage of __slots__?

问题: Python中__slots__的目的是什么-尤其是关于何时以及何时不使用它的目的? 解决方案: 参考一: https://stackoom.com/question/1ymu/slots-的用法 参考二: https://oldbug.net/q/1ym...

富含淀粉
今天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部