[recommend for beginners] Proof of the correctness of best votes solution


  • 0
    F

    I think the code is simple for this problem, but the principle behind the code is a little complicated.
    I only want to share my demonstration for best votes solution.

    The problem can be converted to find the middle node of longest path in original graph, as the MHT is the tree A whose root is the middle node M of longest path, the distance is D.(Let's say two ends are Leaf L1, Leaf L2 ), and Depth(A) = D/2;

    Demonstration:
    (1) If Depth(A) > D/2 and the corresponding leaf is L3. If LCA of L3, L1 is not M, then LCA of L3, L2 must be M, so Distance(L3, L2) longer than D, contradictive, so the Depth(A) = D/2;

    (2) If there is other tree whose node is B node and depth is less than tree A, node B must be internal/leaf node of tree A, the distance between node B and L1 will be greater than depth(A), contradictive. (LCA of node L1 and node B is node M). so treeA is mht for original graph.

    Perform topology-like remove leaf process, the last node must be root node M.

    (1)For tree A, if we use topological-like remove method, then last node must be root node M.

    (2)For original graph, we also use same topological-like remove method, then the last node must be node M.

    Why the result is same? you perform same operation in same data structure, only difference is you image it is a tree in case (1) while it is original graph in case (2). is mht for original graph.

    (1)For tree A, if we use topological-like remove method, then last node must be root node M.

    (2)For original graph, we also use same topological-like remove method, then the last node must be node M.

    Why the result is same, as you perform same operation in same data structure, only difference is you image it is a tree in case (1) while it is original graph in case (2).


Log in to reply
 

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