LeetCode 235. 二叉搜索树的最近公共祖先

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 235. 二叉搜索树的最近公共祖先

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

思路分析

性质利用：在二叉搜索树中，左子树的值小于根节点的值，右子树的值大于根节点的值。

查找过程：

如果 p 和 q 的值都小于当前节点的值，则最近公共祖先在左子树中。

如果 p 和 q 的值都大于当前节点的值，则最近公共祖先在右子树中。

如果 p 和 q 的值分别在当前节点的两侧，当前节点即为最近公共祖先。

参考代码

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	// 从根节点开始查找
	for root != nil {
		// 如果 p 和 q 都小于当前节点，向左子树查找
		if p.Val < root.Val && q.Val < root.Val {
			root = root.Left
		} else if p.Val > root.Val && q.Val > root.Val { // 如果 p 和 q 都大于当前节点，向右子树查找
			root = root.Right
		} else { // 否则，当前节点就是最近公共祖先
			return root
		}
	}
	return nil
}

时间复杂度： O (h)，其中 h 是二叉搜索树的高度。在最坏情况下，树可能是线性的，h = n。 空间复杂度： O (1)，只使用了常数的额外空间。

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	// 如果当前节点为空，直接返回
	if root == nil {
		return nil
	}

	// 如果当前节点的值大于 p 和 q 的值，向左子树查找
	if p.Val < root.Val && q.Val < root.Val {
		return lowestCommonAncestor(root.Left, p, q)
	}

	// 如果当前节点的值小于 p 和 q 的值，向右子树查找
	if p.Val > root.Val && q.Val > root.Val {
		return lowestCommonAncestor(root.Right, p, q)
	}
	
	// 否则，当前节点就是最近公共祖先
	return root
}

首先遍历树，记录每个节点的父节点。

然后从 p 和 q 开始，向上查找其所有祖先，并记录在集合中。

最后遍历 p 的祖先集合，找到第一个出现在 q 的祖先集合中的节点。

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	parent := make(map[*TreeNode]*TreeNode)
	queue := []*TreeNode{root}

	// 记录每个节点的父节点
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]

		if node.Left != nil {
			parent[node.Left] = node
			queue = append(queue, node.Left)
		}

		if node.Right != nil {
			parent[node.Right] = node
			queue = append(queue, node.Right)
		}
	}

	// 查找 p 的所有祖先
	ancestors := map[*TreeNode]bool{}
	for p != nil {
		ancestors[p] = true
		p = parent[p]
	}

	// 查找 q 的祖先，找到第一个出现在 p 的祖先集合中的节点
	for q != nil {
		if ancestors[q] {
			return q
		}
		q = parent[q]
	}

	return nil
}

🍏 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/80298432