[代码随想录]Day17-二叉树part06-526互联

题目：654. 最大二叉树

思路：

和前中序构造树差不多的方法，以前是返回值，现在是返回树

代码：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func constructMaximumBinaryTree(nums []int) *TreeNode {
    if len(nums) == 0 { // 当没有元素了就是结束了
        return nil
    }
    pos := findMaxPos(nums) // 找到最大值
    res := &TreeNode{ // 构建树，左子树是最大值左侧，右子树是最大值右侧
        Val: nums[pos],
        Left: constructMaximumBinaryTree(nums[:pos]),
        Right: constructMaximumBinaryTree(nums[pos+1:]),
    }
    return res
}

func findMaxPos(nums []int) int{
    max := 0
    for i, v := range nums {
        if v > nums[max] {
            max = i
        }
    }
    return max
}

参考：

代码随想录

题目：617. 合并二叉树

思路：

617.合并二叉树.gif

代码：

/**
 * 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 { // 1是空直接取2
        return root2
    }
    if root2 == nil { // 2是空直接取1
        return root1
    }
    root1.Val += root2.Val // 都不是空就加起来
    root1.Left = mergeTrees(root1.Left, root2.Left) // 左子树比左子树
    root1.Right = mergeTrees(root1.Right, root2.Right) // 右子树比右子树
    return root1 // 直接用root1
}

参考：

代码随想录

题目：700. 二叉搜索树中的搜索

思路：

代码1：

递归

func searchBST(root *TreeNode, val int) *TreeNode {
    if root == nil { // 没找到
        return nil
    }
    if root.Val == val { // 找到了直接返回
        return root
    }
    if root.Val > val { // 当比他大时在，去左子树找
        return searchBST(root.Left, val)
    }
    return searchBST(root.Right, val) // 当比他小时，去右子树找
}

代码2：

迭代

/**
 * 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
    }
    for root != nil { // 直到没找到
        if root.Val == val { // 找打了
            return root
        }
        if root.Val > val { // 向左
            root = root.Left
        }else {
            root = root.Right // 向右
        }
    }
    return nil
}

参考：

代码随想录

题目：98. 验证二叉搜索树

思路：

可以是空树，前序，如果根是false，那就没必要向下了。

代码：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    return Calc(root, math.MinInt64, math.MaxInt64)
}

func Calc(root *TreeNode, min, max int) bool {
    if root == nil { // BST可以使空树
        return true
    }
    if root.Val <= min || root.Val >= max {
        return false
    }
    left := Calc(root.Left, min, root.Val)
    right := Calc(root.Right,root.Val, max)
    return left && right
}

参考：