Smallest Subtree with all the Deepest Nodes
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 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]
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.
Solution:
/**
* 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 {
TreeNode result = null;
int maxDepth = 0;
public TreeNode subtreeWithAllDeepest(TreeNode root) {
if(root == null){
return null;
}
findDepthUsingDfs(root, 1);
return result;
}
public int findDepthUsingDfs(TreeNode node, int height){
if(node == null){
return height+1;
}
int left = findDepthUsingDfs(node.left,
height+1);
int right = findDepthUsingDfs(node.right,
height+1);
if(left == right && left >=
maxDepth){
result = node;
maxDepth = left;
}
return Math.max(left, right);
}
}
1) Here, we are using DFS to find depth of each node. At the same time, we are
calculating depth of each node. [left and right in the above code indicates
depth]
2) At any node, if left depth and right depth are same, also if left depth
greater than maximum height, then update the result node and maximum depth
also.
3) Repeat above steps and traverse all node. Finally return the result which
will be the required answer.
Related Posts:
Like us? Please do share with your friends ..!!
Follow us to receive updates instantly.
If you have any feedback/suggestions, leave it in a comment section which will be helpful for us to improve.
Comments
Post a Comment