DEV Community
·
1123. 最深叶子节点的最近公共祖先
💡
原文英文，约1000词，阅读约需4分钟。
📝
内容提要
给定一棵二叉树的根节点，返回其最深叶子节点的最近公共祖先。通过后序遍历计算每个节点的左右子树最大深度，若深度相同，则当前节点为最近公共祖先。该方法的时间复杂度为O(n)，空间复杂度为O(h)。
🎯
关键要点
- 给定一棵二叉树的根节点，返回其最深叶子节点的最近公共祖先。
- 二叉树的叶子节点是没有子节点的节点，根节点的深度为0。
- 最近公共祖先是深度最大的节点，且每个节点都在该节点的子树中。
- 通过后序遍历计算每个节点的左右子树最大深度。
- 若左右子树深度相同，则当前节点为最近公共祖先。
- 该方法的时间复杂度为O(n)，空间复杂度为O(h)。
- 示例1：输入[3,5,1,6,2,0,8,null,null,7,4]，输出为2。
- 示例2：输入[1]，输出为1，根节点即为最深节点。
- 示例3：输入[0,1,3,null,2]，输出为2，最深叶子节点为2。
- 测试用例涵盖了不同结构的树，包括边界情况和更深的叶子节点。
❓
延伸问答
如何找到二叉树中最深叶子节点的最近公共祖先？
通过后序遍历计算每个节点的左右子树最大深度，如果深度相同，则当前节点为最近公共祖先。
什么是二叉树的叶子节点？
二叉树的叶子节点是没有子节点的节点。
该算法的时间复杂度和空间复杂度分别是多少？
该算法的时间复杂度为O(n)，空间复杂度为O(h)。
给定输入[3,5,1,6,2,0,8,null,null,7,4]，输出是什么？
输出为2，这是最深叶子节点的最近公共祖先。
如何判断一个节点是否是最近公共祖先？
如果左右子树的深度相同，则当前节点是最近公共祖先。
最深叶子节点的定义是什么？
最深叶子节点是树中深度最大的叶子节点。
➡️
