给定root
二叉树的 ,每个节点的深度是到根的最短距离。
返回最小的子树,使其包含原始树中所有最深的节点。
如果一个节点在整个树中的任何节点中具有最大的可能深度,则称为最深节点。
节点的子树是由该节点加上该节点所有后代的集合组成的树。
注:本题同1123:https ://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/
示例 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation: We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest nodes of the tree.
Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it.
示例 2:
Input: root = [1]
Output: [1]
Explanation: The root is the deepest node in the tree.
示例 3:
Input: root = [0,1,3,null,2]
Output: [2]
Explanation: The deepest node in the tree is 2, the valid subtrees are the subtrees of nodes 2, 1 and 0 but the subtree of node 2 is the smallest.
约束:
[1, 500]
。0 <= Node.val <= 500
在二叉树中找到一个子树,使它包含所有深度最大的结点。
先一次DFS找到所有最深的结点,然后用找公共祖先的方法递归处理:在当前结点的左子树和右子树中找包含最深结点的子树leftTree和rightTree,如果都存在,说明当前结点是一个公共祖先,返回该结点;如果只有leftTree存在,返回leftTree;如果只有rightTree存在,返回rightTree;如果都不存在,说明以当前结点为根结点的子树不在范围内,返回null。
class Solution {
private Map<TreeNode, Integer> depth = new HashMap<>();
private int maxDepth = -1;
public TreeNode subtreeWithAllDeepest(TreeNode root) {
findDepth(root, 1);
return findAncestor(root);
}
private void findDepth(TreeNode node, int level) {
if (node == null) {
return;
}
maxDepth = Math.max(maxDepth, level);
depth.put(node, level);
findDepth(node.left, level + 1);
findDepth(node.right, level + 1);
}
private TreeNode findAncestor(TreeNode node) {
if (node == null || depth.get(node) == maxDepth) {
return node;
}
TreeNode leftAncestor = findAncestor(node.left);
TreeNode rightAncestor = findAncestor(node.right);
if (leftAncestor != null && rightAncestor != null) {
return node;
} else if (leftAncestor != null) {
return leftAncestor;
} else if (rightAncestor != null) {
return rightAncestor;
} else {
return null;
}
}
}
联系客服