算法_二叉树_二叉树的最近公共祖先

文章目录

二叉树的最近公共祖先

leetcode链接

1.两种解法

递归法–后序遍历

思路:这道题想求两个节点的最近公共祖先,所以我们要从下往上遍历这棵树,并且要先判断两个孩子,然后再去判断根节点的逻辑,所以我们想到使用后序遍历。

对每个节点而言,如果它的左子树中有p(或q),它的右子树中有q(或p),那么当前节点就是他们的最近公共祖先。

所以我们定义单层节点操作逻辑

1.如果当前节点为空,则返回None
2.如果当前节点为p或q,则返回当前节点

为了将该节点的结果传到高层节点上去,对于每个节点还要有传递逻辑

1.如果左孩子传过来的值不为空,表示该节点的左子树中包含p或q,而右孩子传过来的值为空,则把左孩子传过来的值作为该节点的返回值传给更高层。
2.如果左孩子和右孩子同时为空,表示该节点的左右子树中都不包含p和q,所以把None作为该节点的返回值传给更高层。
3.如果左孩子和右孩子都不为空,则表示该节点就是p和q的最近公共祖先,所以把该节点的值作为返回值传给更高层

凭空想象比较难懂,所以给一个例子帮助理解:
算法_二叉树_二叉树的最近公共祖先
分析:图中p为6,q为5。

  1. 后序遍历首先遍历1,根据操作逻辑来看,1不是p和q,也不是空节点,然后看传递逻辑,左孩子和右孩子都是空,则左右孩子都返回None,最后他也返回None给10。
  2. 然后遍历6,根据操作逻辑来看,6为p节点,所以要返回6给7,已经返回了,所以无需传递;
  3. 然后遍历5,根据操作逻辑来看,5为q节点,所以要返回5给7,已经返回了,所以无需传递;
  4. 然后遍历7,根据操作逻辑来看,7不为空,不是p和q,所以不做操作。根据传递逻辑来看,左孩子返回了个6,右孩子返回了个5,都不为空,说明7就是他们的最近公共祖先,所以要返回当前节点的值,也就是7给10。(我们现在要做的就是把7传到根节点,然后让根节点的那层递归返回7即可)
  5. 然后遍历10,根据操作逻辑来看,10不为p和q,也不为空。根据传递逻辑来看,左孩子返回空,右孩子返回7,则该节点返回右孩子的值,也就是7给8
  6. 然后遍历15,…(同样的方法,先看操作逻辑,然后再看传递逻辑)
  7. 然后遍历20,…
  8. 然后遍历4,…,最后4返回None给8
  9. 然后遍历8(根节点),根据操作逻辑来看,8不是p和q,也不是空节点。根据传递逻辑来看,左孩子(10)返回了个7,右孩子(4)返回了个None,所以该节点就要返回左孩子的值,也就是7。这样我们就把7传到了根节点(根节点返回7)。

结合代码来看:

def lowestCommonAncestor(root, p, q):
	# 操作逻辑
    if root==q or root==p or root==None:
        return root

    left = lowestCommonAncestor(root.left,p,q) # 左
    right = lowestCommonAncestor(root.right,p,q) # 右

	# 中
	# 传递逻辑
    if left and right:
        return root
    elif not left and right:
        return right
    elif left and not right:
        return left
    else:
        return None

迭代法–层序遍历

思路:

利用层序遍历结果数组的性质:对于索引为x的节点,他的孩子节点的索引为2x,2x+1

注意:此性质建立在每层节点都要写全的情况下,也就是空节点也要用None填充上。

如果使用层序遍历,把这棵树先遍历一遍,把结果存入result数组中(注意如果每层的节点不满,则要用None填充),那么我们得到p和q在这个数组中的位置,然后让他们重复除以2,直到当他们相等的时候就是公共节点的位置。

虽然我写出了代码,但是会超时,如果有大佬能帮我修改一下减小时间复杂度,我感激不尽:

def lowestCommonAncestor(root, p, q):
	# 用于判断该层是不是最后一层(最后一层的下一层应该全是None)
    def func(queue):
        for i in queue:
            if i != None:
                return True
        return False

    queue = [] 
    result = []
    indexp = -1 # 存放p的索引
    indexq = -1 # 存放q的索引
    count = 0 # 用来计数得到p、q的索引

	'''层序遍历'''
    if root:
        queue.append(root)

    while queue:
        size = len(queue) # 该层的节点数为size
        # 判断该层是不是最后一层的下一层
        if not func(queue):
            break
		
		# 遍历该层节点
        for i in range(size):
            node = queue.pop(0)
            result.append(node)
            count += 1
			
			# 获取索引
            if node == p:
                indexp = count
            if node == q:
                indexq = count
			
			# 空值用None填充
            if node == None:
                queue.append(None)
                queue.append(None)
                continue
			
			# 将左右孩子入队
            queue.append(node.left)
            queue.append(node.right)
	''''''

	# 让indexp作为较大索引,indexq作为较小索引,便于后面操作
    indexp,indexq = max(indexp,indexq),min(indexp,indexq)

	# 让叫大索引indexp先除以2(整型除法),直到<=indexq
    while indexp>indexq:
        indexp = indexp//2

	# 如果等于,则表示q就是p和q的最近公共祖先
    if indexp == indexq:
        return result[indexp-1]
    else: # 如果不相等,我们就交叉除以2,直到他们相等(因为最后肯定会相等,都有同一个根节点)
        while indexp!=indexq:
            if indexp>indexq:
                indexp = indexp//2
            if indexq>indexp:
                indexq = indexq//2
        return result[indexp-1]

2.总结

算法

要善于从题干中得到解题的关键思路。
比如这道题:我们通过两个节点找公共祖先就要先想到用后序遍历。

上一篇:VideoCapture类:


下一篇:java学习记录十二:权限修饰符,代码块,java内部类,自动拆装箱