如何找出排序二叉树上任意两个节点的最近公共父节点？

问题

对于一个给定的排序二叉树，求两个节点的最近公共父节点？

如对于下面这样的二叉树，节点 1 和 6 的最近公共父节点为 4。

解法

对比路径

任意两个点肯定有公共的路径部分，公共路径的最后一个节点就是最近公共父节点。

// 查找 target 在树中的查找路径
func getPath(root *BTNode, target int) []*BTNode {
	var result []*BTNode

	if root == nil {
		return result
	}

	cur := root
	for cur != nil && cur.Data != target {
		result = append(result, cur)
		if cur.Data > target {
			cur = cur.Left
		} else if cur.Data < target {
			cur = cur.Right
		}
	}
	if cur != nil && cur.Data == target {
		result = append(result, cur)
		return result
	}
	// 找不到
	return []*BTNode{}
}

func getLatestParent(path1, path2 []*BTNode) *BTNode {
	if len(path1) == 0 || len(path2) == 0 {
		// 有节点没有找到路径
		return nil
	}
	pos := 0
	for path1[pos] == path2[pos] {
		pos++
	}
	return path1[pos-1]
}

func main() {
	btree := NewBTree(9)
	btree.Left = &BTNode{
		Data: 4,
		Left: &BTNode{Data: 3, Left: &BTNode{Data: 1}},
		Right: &BTNode{
			Data: 6,
			Left: &BTNode{
				Data: 5,
			},
			Right: &BTNode{
				Data: 7,
			},
		},
	}
	btree.Right = &BTNode{
		Data: 14,
		Left: &BTNode{
			Data: 12,
		},
		Right: &BTNode{
			Data: 15,
		},
	}

	path1 := getPath(btree, 1)
	path2 := getPath(btree, 6)

	fmt.Println("节点1的路径：")
	for _, node := range path1 {
		fmt.Printf("%d ", node.Data)
	}
	fmt.Println()

	fmt.Println("节点2的路径：")
	for _, node := range path2 {
		fmt.Printf("%d ", node.Data)
	}
	fmt.Println()

	latestParent := getLatestParent(path1, path2)
	fmt.Println("最近公共父节点：", latestParent.Data)
}

输出：

节点1的路径：
9 4 3 1 
节点2的路径：
9 4 6 
最近公共父节点： 4

时间复杂度为 O(n)，空间复杂度为O(n)。

按完全二叉树进行编号

可以按照完全二叉树中对节点编号，对于任意编号为 n 的父节点，其左节点编号为 n<<1，右节点编号为 n<<1+1。编号时树的根节点编号为1。

示例如下，括号中等号两侧分别为十进制编号，和二进制编号：

对于任意两个节点的公共父节点，可以由两个节点的编号 n»1 计算得到。

如节点3编号为 100，节点7编号为 1011。100>>1=10 、1011>>1>>1=10，结果都为 10，也即节点编号为 2 的节点4。

代码如下：

// 获取指定节点在树中的编号，如果节点不存在，则返回-1
func getNodeNum(parent *BTNode, data int) int {
    if parent == nil {
		// 空树
		return -1
	}
	cur := parent
	// 给 cur 标编号
	num := 1
	for cur != nil && cur.Data != data {
		if cur.Data > data {
			cur = cur.Left
			// 给 cur 标编号
			num = num << 1
		} else if cur.Data < data {
			cur = cur.Right
			// 给 cur 标编号
			num = num<<1 + 1
		}
	}
	if cur != nil && cur.Data == data {
		return num
	}
	return -1
}

// 查找最近公共父节点
// num1 为节点1的编号，num2 为节点2的编号
func getLatestParent(tree *BTNode, num1, num2 int) *BTNode {
	if num1 < 0 || num2 < 0 {
		// 编号有不存在的，则最近公共父节点肯定不存在
		return nil
	}

	for num1 != num2 {
		// num1 和 num2 大的一方除2
		if num1 > num2 {
			num1 = num1 >> 1
		} else if num1 < num2 {
			num2 = num2 >> 1
		}
	}
	// 最后num1会等于num2，也就得到了公共父节点的编号
	latestParentNum := num1

	// 通过最近公共父节点的编号找到节点
	resultParentNode := tree
	tmpNum := 1
	for tmpNum != latestParentNum {
		if tmpNum > latestParentNum {
			resultParentNode = resultParentNode.Right
			tmpNum = tmpNum<<1 + 1
		} else if tmpNum < latestParentNum {
			resultParentNode = resultParentNode.Left
			tmpNum = tmpNum << 1
		}
	}
	return resultParentNode
}


func main() {
	btree := NewBTree(9)
	btree.Left = &BTNode{
		Data: 4,
		Left: &BTNode{Data: 3, Left: &BTNode{Data: 1}},
		Right: &BTNode{
			Data: 6,
			Left: &BTNode{
				Data: 5,
			},
			Right: &BTNode{
				Data: 7,
			},
		},
	}
	btree.Right = &BTNode{
		Data: 14,
		Left: &BTNode{
			Data: 12,
		},
		Right: &BTNode{
			Data: 15,
		},
	}

	num1 := getNodeNum(btree, 3)
	fmt.Println("节点3的编号为：", num1)

	num2 := getNodeNum(btree, 12)
	fmt.Println("节点12的编号为：", num2)

	latestParent := getLatestParent(btree, num1, num2)

	if latestParent == nil {
		fmt.Println("不存在公共父节点")
	} else {
		fmt.Println("最近公共父节点：", latestParent.Data)
	}
}

结果：

节点3的编号为： 4
节点12的编号为： 6
最近公共父节点： 9

后序遍历

后序遍历：左孩子、右孩子、根节点的遍历顺序。

任意两个存在的节点，一定在最近公共父节点的左右两侧，或者其中一个节点就是公共父节点

// 查找 data1 和 data2 在 root 中的公共父节点，返回公共父节点
func getLatestParentNode(root *BTNode, data1, data2 int) *BTNode {
	if root == nil || root.Data == data1 || root.Data == data2 {
		// root 为 nil，则找不到
		// root 为 data1，则公共父节点为 data1，data2 在data1下面
		// root 为 data2，则公共父节点为 data2，data1 在data2下面
		return root
	}
	// 从左侧查找公共父节点
	lChild := getLatestParentNode(root.Left, data1, data2)
	// 从右侧查找公共父节点
	rChild := getLatestParentNode(root.Right, data1, data2)
	if lChild == nil {
		// 左侧查不到，在右侧
		return rChild
	}
	if rChild == nil {
		// 右侧查不到，在左侧
		return lChild
	}
	// root 就是最近的公共父节点 
	return root
}

func main() {
	btree := NewBTree(9)
	btree.Left = &BTNode{
		Data: 4,
		Left: &BTNode{Data: 3, Left: &BTNode{Data: 1}},
		Right: &BTNode{
			Data: 6,
			Left: &BTNode{
				Data: 5,
			},
			Right: &BTNode{
				Data: 7,
			},
		},
	}
	btree.Right = &BTNode{
		Data: 14,
		Left: &BTNode{
			Data: 12,
		},
		Right: &BTNode{
			Data: 15,
		},
	}

	latestParent := getLatestParent(btree, 5, 1)

	if latestParent == nil {
		fmt.Println("不存在公共父节点")
	} else {
		fmt.Println("最近公共父节点：", latestParent.Data)
	}
}

结果：

最近公共父节点： 4