@@ -0,0 +1,2190 @@
+package tree.bottom_up;%0A%0Aimport public_class.TreeNode;%0A%0Apublic class Q998MaximumBinaryTreeII %7B%0A%0A    //Difficulty: Medium%0A    //TAG: Tree%0A    //TAG: post order%0A%0A    /**%0A     * 998. Maximum Binary Tree II%0A     * We are given the root node of a maximum tree: a tree where every node has a value greater than any other value in its subtree.%0A     *%0A     * Just as in the previous problem, the given tree was constructed from an list A (root = Construct(A)) recursively with the following Construct(A) routine:%0A     *%0A     * If A is empty, return null.%0A     * Otherwise, let A%5Bi%5D be the largest element of A.  Create a root node with value A%5Bi%5D.%0A     * The left child of root will be Construct(%5BA%5B0%5D, A%5B1%5D, ..., A%5Bi-1%5D%5D)%0A     * The right child of root will be Construct(%5BA%5Bi+1%5D, A%5Bi+2%5D, ..., A%5BA.length - 1%5D%5D)%0A     * Return root.%0A     * Note that we were not given A directly, only a root node root = Construct(A).%0A     *%0A     * Suppose B is a copy of A with the value val appended to it.  It is guaranteed that B has unique values.%0A     *%0A     * Return Construct(B).%0A     *%0A     *%0A     *%0A     * Example 1:%0A     *%0A     *%0A     *%0A     * Input: root = %5B4,1,3,null,null,2%5D, val = 5%0A     * Output: %5B5,4,null,1,3,null,null,2%5D%0A     * Explanation: A = %5B1,4,2,3%5D, B = %5B1,4,2,3,5%5D%0A     * Example 2:%0A     *%0A     *%0A     * Input: root = %5B5,2,4,null,1%5D, val = 3%0A     * Output: %5B5,2,4,null,1,null,3%5D%0A     * Explanation: A = %5B2,1,5,4%5D, B = %5B2,1,5,4,3%5D%0A     * Example 3:%0A     *%0A     *%0A     * Input: root = %5B5,2,3,null,1%5D, val = 4%0A     * Output: %5B5,2,4,null,1,3%5D%0A     * Explanation: A = %5B2,1,5,3%5D, B = %5B2,1,5,3,4%5D%0A     *%0A     *%0A     * Note:%0A     *%0A     * 1 %3C= B.length %3C= 100%0A     */%0A%0A    /*%0A    Solution:%0A    Insert node always at most right place, or append rest of smaller value to left subtree%0A%0A    Time: O(n)%0A    Space: O(n)%0A     */%0A%0A    public TreeNode insertIntoMaxTree(TreeNode root, int val) %7B%0A        if (root == null) return new TreeNode(val);%0A        else if (root.val %3C val) %7B%0A            TreeNode node = new TreeNode(val);%0A            node.left = root;%0A            return node;%0A        %7D else %7B%0A            root.right = insertIntoMaxTree(root.right, val);%0A            return root;%0A        %7D%0A    %7D%0A%0A%7D%0A

998. Maximum Binary Tree II