美文网首页
865.求最深公共子树

865.求最深公共子树

作者: 愛與誠 | 来源:发表于2020-05-29 18:12 被阅读0次

给定一个根为 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(); 
}

相关文章

  • 865.求最深公共子树

    给定一个根为 root 的二叉树,每个结点的深度是它到根的最短距离。 如果一个结点在整个树的任意结点之间具有最大的...

  • Leetcode 865. 具有所有最深结点的最小子树(后序遍历

    问题描述 给定一个根为 root 的二叉树,每个结点的深度是它到根的最短距离。如果一个结点在整个树的任意结点之间具...

  • 每日算法题—包含所有最深结点的最小子树

    题目描述 给定一棵二叉树,求包含所有最深节点的最小子树最深节点:深度最大的节点,深度即当前节点到根节点的最短距离包...

  • 最长公共 / 对称字串

    求最长对称字串是求最长公共子串的变形.. (๑˘ ˘๑) 最长公共子串 Longest Common Subseq...

  • 面试题68:树中两个节点的最低公共祖先

    题目 输入两个树节点,求它们的最低公共祖先 解题思路 若该树为二叉搜索树 因为二叉搜索树是排过序的,位于左子树的节...

  • 236. Lowest Common Ancestor of a

    二叉树最近公共祖先,dfs,当且仅当左子树与右子树都属于一个节点或根节点为其中一个元素的情况下,找到最近公共祖先。...

  • 二叉树相关题

    二叉树的最低公共祖先 中序遍历的后继 有右子树 则是右子树上最左节点 没有右子树 后继Y 符合左树中最右的节点是...

  • 动态规划

    1、求最长公共子序列 2、求最长公共子串 3、0-1背包问题 4、最短编辑距离

  • [LeetCode OJ]- Maximum Depth of

    题目要求:求一颗二叉树的最大深度 思路:递归+左右子树深度比较,当子树为空时,返回0

  • [LeetCode OJ]- Minimum Depth of

    题目要求:求一颗二叉树的最小深度 思路:递归+左右子树深度比较,当子树为空时,返回0

网友评论

      本文标题:865.求最深公共子树

      本文链接:https://www.haomeiwen.com/subject/bzqiahtx.html