Leetcode 998. Maximum Binary Tree II

Given a maximum binary tree and a value val appended to the original array, produce the new maximum tree that would result from appending val — this is done by placing val along the tree's right spine so the max-tree property (each node > values in its subtree) is preserved.