【二叉树】最大二叉树 II

0x00 题目

最大树定义：
一棵树，其中每个节点的值
都大于其子树中的任何其他值
给你最大树的根节点 root 和一个整数 val
把 val 插入这棵树
并返回新的最大二叉树的根节点

---

0x01 思路

根据构建最大二叉树的规则
根节点是给定数组中的最大值
最大值左边是左子树
最大值右边是右子树

新插入的 val 是添加在给定数组最后的
所以 val 应该插入到右子树

---

0x02 解法

语言：Swift

树节点：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
    }
}

解法：

func insertIntoMaxTree(_ root: TreeNode?, _ val: Int) -> TreeNode? {
    // 节点为空，则返回一个新节点
    guard let r = root else { return TreeNode(val) }
    
    // 节点值比插入值小，则找到位置
    if r.val < val {
        let node = TreeNode(val)
        node.left = r
        return node
    }
    
    // 插入到右子树
    r.right = insertIntoMaxTree(r.right, val)
    return r
}

---

0x03 我的作品

欢迎体验我的作品之一：小编辑器
小巧的在线编辑器
包含多种语言
App Store 搜索即可~

---