998. Maximum Binary Tree II

Problem Statement

link: LeetCode.cn LeetCode A maximum tree is a tree where every node has a value greater than any other value in its subtree.

You are given the root of a maximum binary tree and an integer val.

Just as in the previous problem, the given tree was constructed from a list a (root = Construct(a)) recursively with the following Construct(a) routine:

If a is empty, return null. Otherwise, let a[i] be the largest element of a. Create a root node with the value a[i]. The left child of root will be Construct([a[0], a[1], …, a[i - 1]]). The right child of root will be Construct([a[i + 1], a[i + 2], …, a[a.length - 1]]). Return root. Note that we were not given a directly, only a root node root = Construct(a).

Suppose b is a copy of a with the value val appended to it. It is guaranteed that b has unique values.

Return Construct(b).

Example:

Input: root = [4,1,3,null,null,2], val = 5 Output: [5,4,null,1,3,null,null,2]

Input: root = [5,2,4,null,1], val = 3 Output: [5,2,4,null,1,null,3]

Input: root = [5,2,3,null,1], val = 4 Output: [5,2,4,null,1,3]

Constraints: The number of nodes in the tree is in the range [1, 100]. 1 <= Node.val <= 100 All the values of the tree are unique. 1 <= val <= 100

Solution Approach

The solution involves traversing the rightmost path of the tree, inserting the new value at the appropriate position where it maintains the maximum binary tree property, either as a new root or as the right child of an existing node.

Algorithm

1. Traverse Right Path: Start at the root and traverse down the rightmost path, since the new value is only relevant to the nodes on this path in maintaining the maximum property.
2. Insert New Value: If the new value is greater than the current node, insert it as a new root of the subtree with the current node as its left child. Otherwise, continue down the path until finding the correct position.
3. Update Tree Structure: Once the correct position is found, either attach the new node as a right child or restructure the subtree to maintain the maximum binary tree property.

Implement

    class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        parent, cur = None, root
        while cur:
            if val > cur.val:
                if not parent:
                    return TreeNode(val, root, None)
                node = TreeNode(val, cur, None)
                parent.right = node
                return root
            else:
                parent = cur
                cur = cur.right
        parent.right = TreeNode(val)
        return root


    

    
    

Twitter  facebook  Email