Description
Given the root of a binary tree, the depth of each node is the shortest distance to the root.
Return the smallest subtree such that it contains all the deepest nodes in the original tree.
A node is called the deepest if it has the largest depth possible among any node in the entire tree.
The subtree of a node is a tree consisting of that node, plus the set of all descendants of that node.
Example 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.
Example 2:
Input: root = [1]
Output: [1]
Explanation: The root is the deepest node in the tree.
Example 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.
Constraints:
- The number of nodes in the tree will be in the range
[1, 500].
0 <= Node.val <= 500- The values of the nodes in the tree are unique.
Note: This question is the same as 1123: https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/
Solutions
Solution 1: Recursion
We design a function dfs(root) that returns the smallest subtree containing all the deepest nodes in the subtree rooted at root, as well as the depth of the subtree rooted at root.
The execution process of the function dfs(root) is as follows:
- If root is null, return null and 0.
- Otherwise, recursively calculate the smallest subtree and depth of the left and right subtrees of root, denoted as l and ld, and r and rd, respectively. If ld > rd, then the smallest subtree containing all the deepest nodes in the subtree rooted at the left child of root is l, with a depth of ld + 1. If ld < rd, then the smallest subtree containing all the deepest nodes in the subtree rooted at the right child of root is r, with a depth of rd + 1. If ld = rd, then root is the smallest subtree containing all the deepest nodes, with a depth of ld + 1.
Finally, return the first element of the result of dfs(root).
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
PythonJavaC++GoTypeScriptRust
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def subtreeWithAllDeepest(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def dfs(root: Optional[TreeNode]) -> Tuple[Optional[TreeNode], int]:
if root is None:
return None, 0
l, ld = dfs(root.left)
r, rd = dfs(root.right)
if ld > rd:
return l, ld + 1
if ld < rd:
return r, rd + 1
return root, ld + 1
return dfs(root)[0](code-box)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode subtreeWithAllDeepest(TreeNode root) {
return dfs(root).getKey();
}
private Pair<TreeNode, Integer> dfs(TreeNode root) {
if (root == null) {
return new Pair<>(null, 0);
}
var l = dfs(root.left);
var r = dfs(root.right);
int ld = l.getValue(), rd = r.getValue();
if (ld > rd) {
return new Pair<>(l.getKey(), ld + 1);
}
if (ld < rd) {
return new Pair<>(r.getKey(), rd + 1);
}
return new Pair<>(root, ld + 1);
}
}(code-box)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* subtreeWithAllDeepest(TreeNode* root) {
using pti = pair<TreeNode*, int>;
auto dfs = [&](this auto&& dfs, TreeNode* root) -> pti {
if (!root) {
return {nullptr, 0};
}
auto [l, ld] = dfs(root->left);
auto [r, rd] = dfs(root->right);
if (ld > rd) {
return {l, ld + 1};
}
if (ld < rd) {
return {r, rd + 1};
}
return {root, ld + 1};
};
return dfs(root).first;
}
};(code-box)
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func subtreeWithAllDeepest(root *TreeNode) *TreeNode {
type pair struct {
node *TreeNode
depth int
}
var dfs func(*TreeNode) pair
dfs = func(root *TreeNode) pair {
if root == nil {
return pair{nil, 0}
}
l, r := dfs(root.Left), dfs(root.Right)
ld, rd := l.depth, r.depth
if ld > rd {
return pair{l.node, ld + 1}
}
if ld < rd {
return pair{r.node, rd + 1}
}
return pair{root, ld + 1}
}
return dfs(root).node
}(code-box)
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function subtreeWithAllDeepest(root: TreeNode | null): TreeNode | null {
const dfs = (root: TreeNode | null): [TreeNode, number] => {
if (!root) {
return [null, 0];
}
const [l, ld] = dfs(root.left);
const [r, rd] = dfs(root.right);
if (ld > rd) {
return [l, ld + 1];
}
if (ld < rd) {
return [r, rd + 1];
}
return [root, ld + 1];
};
return dfs(root)[0];
}(code-box)
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn subtree_with_all_deepest(
root: Option<Rc<RefCell<TreeNode>>>,
) -> Option<Rc<RefCell<TreeNode>>> {
fn dfs(
root: Option<Rc<RefCell<TreeNode>>>,
) -> (Option<Rc<RefCell<TreeNode>>>, i32) {
if let Some(node) = root {
let left = node.borrow().left.clone();
let right = node.borrow().right.clone();
let (l, ld) = dfs(left);
let (r, rd) = dfs(right);
if ld > rd {
(l, ld + 1)
} else if ld < rd {
(r, rd + 1)
} else {
(Some(node), ld + 1)
}
} else {
(None, 0)
}
}
dfs(root).0
}
}(code-box)
