[leetcode 算法练习] 寻找包含所有最深的结点的子树

电玩女神 2022-04-04 03:52 148阅读 0赞

## 题目 ##

给定一个根为 root 的`二叉树`，每个结点的深度是它到根的最短距离。  
如果一个结点在整个树的任意结点之间具有最大的深度，则该结点是最深的。  
一个结点的子树是该结点加上它的所有后代的集合。  
返回能满足“以该结点为根的子树中包含所有最深的结点”这一条件的具有最大深度的结点。

> 提示：  
> 树中结点的数量介于 1 和 500 之间。  
> 每个结点的值都是独一无二的。

## 示例： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0MjA4ODQ0_size_16_color_FFFFFF_t_70]

## 解题思路 ##

最终要的结果是返回包含`所有` `最深`节点的`子树`(包括本身)

1.  计算根节点左边和右边的最大深度(如果深度一样, 则答案就是它本身)
2.  递归计算深度较大的一边的深度直到比较完所有子数

public TreeNode subtreeWithAllDeepest(TreeNode root) { 
    	if (root == null) { 
    		return null;
    	}
    
    	long left = 0;
    	long right = 0;
    
    	left = findDeepest(root.left);
    	right = findDeepest(root.right);
    
    	if (left == right) return root;
    	if (left > right) { 
    		return subtreeWithAllDeepest(root.left);
    	} else { 
    		return subtreeWithAllDeepest(root.right);
    	}
    }
    
    private long findDeepest(TreeNode node) { 
    	if (node == null) { 
    		return 0;
    	}
    	return Math.max(findDeepest(node.left), findDeepest(node.right)) + 1;
    }

## 扩展 ##

题目我们是解出来了, 但是最要命的是有个提示, 说明肯定有更高效的算法(这种暴力遍历确实不够高效)

>  *  树中结点的数量介于 1 和 500 之间。
>  *  每个结点的值都是独一无二的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0MjA4ODQ0_size_16_color_FFFFFF_t_70]: /images/20220404/80633681a28a4d46a38624174db9d203.png