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

Categories:

Tags:

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

题目描述

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

思路分析

使用队列：我们可以使用队列进行层序遍历，同时记录每个节点的父节点。

记录父节点：在遍历过程中，使用一个哈希表来记录每个节点的父节点。

查找路径：从 p 和 q 开始，分别向上查找其所有祖先，并记录在集合中。

找到最近公共祖先：遍历 p 的祖先集合，找到第一个出现在 q 的祖先集合中的节点，即为最近公共祖先。

参考代码

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	// 使用队列来进行层序遍历
	queue := []*TreeNode{root}
	parent := make(map[*TreeNode]*TreeNode)

	// 记录每个节点的父节点
	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
}

时间复杂度： O(n)，其中 n 是二叉树的节点数量。我们需要遍历每个节点一次。 空间复杂度： O(n)，用于存储父节点的哈希表和队列。

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

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

	if left != nil && right != nil {
		return root
	}
	
	if left != nil {
		return left
	}

	return right
}

时间复杂度： O(n)，其中 n 是二叉树的节点数量。我们需要遍历每个节点一次。 空间复杂度： O(h)，其中 h 是二叉树的高度。最坏情况下，递归栈的深度为树的高度。

🍏 点击查看 Java 题解

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else {
            return right;
        }
    }
}

本文作者: HGNULB

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