给定一个根为 root 的二叉树,每个结点的深度是它到根的最短距离。
如果一个结点在整个树的任意结点之间具有最大的深度,则该结点是最深的。
一个结点的子树是该结点加上它的所有后代的集合。
返回能满足“以该结点为根的子树中包含所有最深的结点”这一条件的具有最大深度的结点。
方法一:
二次dfs
做一次深度搜索 记录下每个点的深度
找深度其实要利用到父节点,不管是左还是右子树,通常都是父节点加1
用数学的函数遍历并且记录下深度最大的值,便于比较
第二次深度搜索 是为了找到 深度最大的子树的节点 真正的求答案
'''
class Solution {
Map<TreeNode, Integer> depth;
int max_depth;
public TreeNode subtreeWithAllDeepest(TreeNode root) {
depth = new HashMap();
depth.put(null, -1); //首层是1还是0不重要 因为不是求深度
dfs(root, null);//这里两个null表示父节点
max_depth = -1;//初始化
for (Integer d: depth.values())
max_depth = Math.max(max_depth, d);
return answer(root);
}
public void dfs(TreeNode node, TreeNode parent) {
if (node != null) {
depth.put(node, depth.get(parent) + 1); 记录深度
dfs(node.left, node)
dfs(node.right, node);
}
}
public TreeNode answer(TreeNode node) {//始终只是中间过程而已
if (node == null || depth.get(node) == max_depth) //这个点为空 或者已经是最大深度了 答案
return node;
TreeNode L = answer(node.left), //如果左子树为空 方法体里返回的node也会为空的 找到则为左最深
R = answer(node.right);//同上的 找到则为右最深
if (L != null && R != null) return node; //从上面的条件可以看到 如果左右均不为空 那么说明左右都有最大深度了,那么这个点就是要找的点
if (L != null) return L; //说明在左子树中
if (R != null) return R;
return null; //左右子树都没 只要找不到最深的 都为 null
}
}
作者:LeetCode
链接:https://leetcode-cn.com/problems/smallest-subtree-with-all-the-deepest-nodes/solution/ju-you-suo-you-zui-shen-jie-dian-de-zui-xiao-zi-sh/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
时间空间复杂度都为o(N),即考虑最坏情况,都需要遍历N次,申请N个空间
这里有个小技巧,一般来说使用递归都会让时间空间复杂度变成o(N),说得不对请轻喷
方法二:
一次dfs
主要利用自定义的类 用于返回结果和存储
递归的思想还是需要好好磨炼 ,个人觉得递归就是一种基于整体已实现的思路
(1)如果左右子树的深度相等,那么就返回node节点
(2)如果左子树大于右子树,则返回左节点,否则返回右节点
public treenode dfs(Treenode node){
if(node==null) return new(null,0);
TReenode L= dfs();
}
网友评论