力扣刷题日记_day1 类别：二叉树

1.0.1、108将有序数组转换为二叉搜索数

难度：easy 思路递归
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

递归三部曲

• 确定递归函数返回值及其参数
• 确定递归终止条件
• 确定单层递归的逻辑

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedArrayToBST(nums []int) *TreeNode {
	return helper(nums, 0, len(nums) - 1)
}

func helper(nums []int, left, right int) *TreeNode {
    //递归结束条件 左右指针相撞
	if left > right {
		return nil
	}
    //方法一：中序遍历，总是选择中间位置左边的数字作为根节点
	mid := left + (right - left) / 2 //防溢出
	root := &TreeNode{Val: nums[mid]}
	root.Left = helper(nums, left,mid - 1)
	root.Right = helper(nums, mid + 1, right)
	return root
}

1.0.2、110平衡二叉树

难度：easy 思路递归
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

func isBalanced(root *TreeNode) bool {
	if root == nil {
        //依题意如果根为空那就返回true
		return true
	}
    //如果左子树和右子树高度差的绝对值不超过 1就是平衡二叉树 递归所有左子树的左子树和右子树的右子树
	return abs(height(root.Left) - height(root.Right)) <= 1 && isBalanced(root.Left) && isBalanced(root.Right)
}

//计算树的高度
func height(root *TreeNode) int{
	if root == nil {
		return 0
	}
	return max(height(root.Left), height(root.Right)) + 1
}
//最大值
func max(a, b int) int{
	if a > b {
		return a
	}
	return b
}
//绝对值
func abs(a int) int{
	if a < 0 {
		return -a
	}
	return a
}