Simple explanation for final results will not more than 2.

  • 0

    I think it is not that obvious, so I try and draw a little bit finally figure out.
    Firstly, what MHT means is NOT the minimum height from current root to any leaf.
    Let's say there's a graph goes like this[[7,3],[3,2],[2,4],[4,8],[2,5],[5,9],[2,1],[1,6]]. You can see node 2 is the middle point of this graph, can we pick 3,4,5 or 1 as root with minimum height? No. Cuz as mentioned before, it's NOT from root to any leaf but root to farthest leaf. In that case, the only result is middle point, 2.
    Ok, now let's say how many points can be final results. The answer is 2. Think about a simple situation, the final situation goes like [1,2], in that case, when we pick node 1, minimum height is 1, when we pick node 2, minimum height is still 1. So both can work as results. What if we got situation like [[1,2],[2,3]], can we list nodes 1,2,3 as results? No, since 2 is between 1 and 3, height of 1 and 3 are both 2, but height of 2 is only 1, which means, both 1 and 3 still are leaf.

    Hope above explanation will help with understanding the constraints of cutting leaves.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.