树中两个节点的最低公共祖先

Published 2019-04-15 07:45:14

在《剑指Offer》7.2 章中,面试案例:树中两个节点的最低公共祖先,记录了如下面试流程:

面试官:让我们做一个编程题目吧。输入树的两个节点,求他们的最低公共祖先。
面试者:这树是不是二叉树呢?
面试官:是又怎么样,不是又怎么样?
应聘者:如果是二叉树,并且是二叉搜索树,是可以找到公共节点的。
面试官:那假如就是二叉搜索树,你怎么查找呢?

二叉搜索树的查找:

func lowestCommonAncestor(root, p, q *structure.TreeNode) *structure.TreeNode {
	if root == nil || p == nil || q == nil {
		return nil
	}

	switch {
	case q.Val < root.Val && p.Val < root.Val:
		return lowestCommonAncestor(root.Left, p, q)
	case q.Val > root.Val && p.Val > root.Val:
		return lowestCommonAncestor(root.Right, p, q)
	}

	return root
}
面试官:看来你对这个题目很熟悉呢。
应聘者:这个碰巧。
面试官:那咱们稍微换一下,如果这棵树不是二叉搜索树,只是二叉树,又该怎么办?(此处我做了稍微的改动,原题为普通树)

二叉树:

func lowestCommonAncestor(root, p, q *structure.TreeNode) *structure.TreeNode {
	if root == nil {
		return nil
	}
	if root.Val == p.Val || root.Val == q.Val {
		return root
	}

	left := lowestCommonAncestor(root.Left, p, q)
	right := lowestCommonAncestor(root.Right, p, q)

	switch {
	case left == nil:
		return right
	case right == nil:
		return left
	}

	return root
}
面试官:小伙汁,可以呀,那咱们在稍微改一下,如果这只是一颗普通的树呢?
应聘者:树的节点中有没有指向父节点的指针呢?
面试官:为什么需要指向父节点的指针?
应聘者:如果存在指向父节点的指针,这个问题可以转换成求两个链表的第一个公共节点。
……

链表

func getIntersectionNode(headA, headB *structure.ListNode) *structure.ListNode {
	if headA == nil || headB == nil {
		return nil
	}
	a, b := headA, headB
	la, lb := 0, 0
	for a != nil {
		a = a.Next
		la++
	}
	for b != nil {
		b = b.Next
		lb++
	}

	if la > lb {
		abs := la - lb
		for ; abs > 0; abs-- {
			headA = headA.Next
		}
	} else {
		abs := lb - la
		for ; abs > 0; abs-- {
			headB = headB.Next
		}
	}
	for headA != nil && headB != nil {
		if headA.Val == headB.Val {
			return headA
		}
		headA = headA.Next
		headB = headB.Next
	}
	return nil
}
面试官:那如果这就是颗普通的树,而且没有指向父节点的指针,你改如何处理?
应聘者:我们可以遍历整棵树,需找输入的两个节点p、q,将root节点到p、q的路径存储到两个链表,
这样就可以转换为上面的问题了,求两个链表的最近公共祖先。
……

参考资料

剑指Offer

leetcode 160

leetcode 235

leetcode 236