[Leetcode] Problem 865 - Smallest Subtree with all the Deepest Nodes

Posted on | In ,

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

No.1

0cwoeP.png

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.

No.2

Input: root = [1]

Output: [1]

Explanation: The root is the deepest node in the tree.

No.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].
  • The values of the nodes in the tree are unique.

Code

1
2
3
4
5
6
7
8
9
10
11
12
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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Node {
    private int height;
    private TreeNode node;

    public Node(int height, TreeNode node) {
        this.height = height;
        this.node = node;
    }
}

public TreeNode subtreeWithAllDeepest(TreeNode root) {
    return dfs(root).node;
}

private Node dfs(TreeNode root) {
    if (root == null)
        return new Node(-1, null);

    Node left = dfs(root.left);
    Node right = dfs(root.right);

    int height = Math.max(left.height, right.height) + 1;
    TreeNode node = left.height == right.height ? root : (left.height > right.height ? left.node : right.node);
    return new Node(height, node);
}