当前位置：网站首页>[binary tree] maximum binary tree II

[binary tree] maximum binary tree II

2022-06-30 01:29:00 【It's so cold】

0x00 subject

The biggest tree Definition ：
A tree , among Every The value of the node
all Greater than Any other value in its subtree
Give you the root node of the largest tree root And an integer val
hold val Insert this tree
And return the new largest binary tree root node

0x01 Ideas

According to the The rules
root The nodes are in a given array Maximum value
Maximum On the left yes Left subtree
Maximum On the right yes Right subtree

Newly inserted val Is added to a given array Last Of
therefore val Should be inserted into Right subtree

0x02 solution

Language ：Swift

Tree node ：TreeNode

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

solution ：

func insertIntoMaxTree(_ root: TreeNode?, _ val: Int) -> TreeNode? {
    //  Node is empty , Then a new node is returned 
    guard let r = root else { return TreeNode(val) }
    
    //  Node value is smaller than insert value , Find the location 
    if r.val < val {
        let node = TreeNode(val)
        node.left = r
        return node
    }
    
    //  Insert into the right subtree 
    r.right = insertIntoMaxTree(r.right, val)
    return r
}