题目：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. 合并二叉树
思路：
代码：
/**
* 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
}