LeetCode 剑指 Offer 68 - II. 二叉树的最近公共祖先

Categories:

题目描述
思路分析
1. 解法一：递归后序遍历（推荐）
相似题目

题目描述

✅ 剑指 Offer 68 - II. 二叉树的最近公共祖先

思路分析

解法一：递归后序遍历（推荐）

核心思路：

在左右子树递归查找 p、q。

若左右都返回非空，当前节点即为 LCA。

若只有一侧非空，则返回那一侧。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数。

空间复杂度：O(h)，其中 h 表示树高。

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;
        }
        return left != null ? left : right;
    }
}

func lowestCommonAncestor(root *TreeNode, p *TreeNode, 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
}

相似题目

题目	难度	考察点
236. 二叉树的最近公共祖先	中等	树递归
235. 二叉搜索树的最近公共祖先	简单	BST
1644. 二叉树的最近公共祖先 II	中等	树递归
1123. 最深叶节点的最近公共祖先	中等	树递归
102. 二叉树的层序遍历	中等	树遍历

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/24707848