654.最大二叉树

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func construct(nums []int, l int, r int) *TreeNode {
    if l > r || l >= len(nums) || r >= len(nums) || l < 0 || r < 0 {
        return nil
    }
    maxIndex := l
    // find max
    for i := l + 1; i <= r; i++ {
        if nums[i] > nums[maxIndex] {
            maxIndex = i
        }
    }
    // create node
    node := &TreeNode{Val: nums[maxIndex]}
    // left and right
    node.Left = construct(nums, l, maxIndex-1)
    node.Right = construct(nums, maxIndex+1, r)
    return node
}
func constructMaximumBinaryTree(nums []int) *TreeNode {
    return construct(nums, 0, len(nums)-1)
}

617.合并二叉树

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil && root2 == nil {
        return nil
    }
    if root1 == nil && root2 != nil{
        return root2
    }
    if root2 == nil && root1 != nil{
        return root1
    }
    // merge tree
    mergedTree := &TreeNode{
        Val: root1.Val+root2.Val,
        Left: mergeTrees(root1.Left, root2.Left),
        Right: mergeTrees(root1.Right, root2.Right),
    }

    return mergedTree
}

700.二叉搜索树中的搜索

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func searchBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return nil
    }
    rootVal := root.Val
    if rootVal == val {
        return root
    }
    if rootVal > val {
        return searchBST(root.Left, val)
    } else {
        return searchBST(root.Right, val)
    }
    return nil
}

98.验证二叉搜索树

• 中序升序

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var orderRes []int
func inOrder(root *TreeNode) {
    if root == nil {
        return 
    }
    // in order
    inOrder(root.Left)
    orderRes = append(orderRes, root.Val)
    inOrder(root.Right)
}
func isValidBST(root *TreeNode) bool {
    orderRes = []int{}
    inOrder(root)
    for i := 1; i < len(orderRes); i++ {
        if orderRes[i] <= orderRes[i-1] {
            return false
        }
    } 
    return true
}

---

• 分类： 未分类
• 标签： 无标签