type
status
date
slug
summary
tags
category
icon
password
一道DFS题目，巩固DFS的思想。
📝 题目
给你一个有根节点
root 的二叉树，返回它 最深的叶节点的最近公共祖先 。回想一下：
- 叶节点 是二叉树中没有子节点的节点
- 树的根节点的 深度 为
0，如果某一节点的深度为d，那它的子节点的深度就是d+1
- 如果我们假定
A是一组节点S的 最近公共祖先，S中的每个节点都在以A为根节点的子树中，且A的深度达到此条件下可能的最大值。
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4] 输出：[2,7,4] 解释：我们返回值为 2 的节点，在图中用黄色标记。 在图中用蓝色标记的是树的最深的节点。 注意，节点 6、0 和 8 也是叶节点，但是它们的深度是 2 ，而节点 7 和 4 的深度是 3 。
示例 2：
输入：root = [1] 输出：[1] 解释：根节点是树中最深的节点，它是它本身的最近公共祖先。
示例 3：
输入：root = [0,1,3,null,2] 输出：[2] 解释：树中最深的叶节点是 2 ，最近公共祖先是它自己。
提示：
- 树中的节点数将在
[1, 1000]的范围内。
0 <= Node.val <= 1000
- 每个节点的值都是 独一无二 的。
🤗 解法
利用DFS的算法从最底层的根开始向上递增，最底层的空节点设为0层，然后向上递归，每递归一层，深度+1，比较每一个节点左右递归上来的节点的深度，此时有三种情况。
- 如果两个左右子节点的深度相同说明这个节点正是这一条分支最深叶节点的最近公共祖先，返回这个节点与它的深度+1
- 如果左子节点的深度大于右子节点，说明我们要找的最深叶节点的最近公共祖先在左子节点那一分支，返回左子节点与它的深度+1
- 反之亦然
📎 参考文章
- LeetCode Wiki
如果有这篇文章的什么问题，欢迎您在底部评论区留言，一起交流~
- Author:灵檠
- URL:https://blog.ly-qing.lol/article/5ac5d994-139a-494a-93d0-ce4c36f3c0d6
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!