第一周 二叉树

今年又开始了，今天主要是总结上两周的做题记录，这几天还是有点放松，懈怠了，必须要抓紧了

上周主要完成了简单的二叉树算法题

二叉树的中序遍历

这题主要是开始复习二叉树的遍历，需要学习的知识分别是二叉树的前序，中序，以及后序遍历，同时需要关注针对递归返回的数组怎么处理

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    if root == nil{
        return nil
    }
    var ret []int
    if root.Left != nil{
        ret = append(ret,inorderTraversal(root.Left)...)
    }
    ret = append(ret,root.Val)
    if root.Right != nil{
        ret = append(ret,inorderTraversal(root.Right)...)
    }
    return ret
}

相同的树

这题一样也就比较简单了，之前会先思考通过遍历的方式，获取到一个数组，然后判断两个数组是否相等
但是同样的，可以通过递归进行处理，这题就和镜像树的逻辑大同小异了

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil{
        return true
    }
    if p == nil || q == nil{
        return false
    }
    if p.Val != q.Val{
        return false
    }
    return isSameTree(p.Left,q.Left)&&isSameTree(p.Right,q.Right)
}

翻转二叉树

这题还是比较看重结题思路的，优先演绎一下怎么进行翻转，可以发现，通过交换每个根节点的左右的节点，就能实现对二叉树的翻转

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func invertTree(root *TreeNode) *TreeNode {
    if root == nil{
        return root
    }
    if root.Left == nil && root.Right==nil{
        return root
    }
    var ret = root.Left
    root.Left = root.Right
    root.Right = ret
    invertTree(root.Left)
    invertTree(root.Right)
    return root
}

叉树的最大最小深度

最小深度因为需要考虑空节点的情况，所以边界条件较多
当根节点有一个为子节点为空的情况下，应该返回较大的节点数
当根节点两个子节点都为空的情况下，直接返回0
当根节点两个子节点都不为空的情况下，直接返回较小的

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDepth(root *TreeNode) int {
    if root == nil{
        return 0
    }
    lDepth := minDepth(root.Left)
    rDepth := minDepth(root.Right)
    if  lDepth == 0{
        return rDepth +1
    }
    if rDepth == 0{
        return lDepth +1
    }
    if lDepth <= rDepth {
        return lDepth+1
    }
    return rDepth + 1
}

最大深度不需要考虑结果的边界情况

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
    if root == nil{
        return 0
    }
    leftRet := maxDepth(root.Left)
    rightRet := maxDepth(root.Right)
    if leftRet+1 >=rightRet+1{
        return leftRet+1
    }
    return rightRet+1
}

将有序数组转换为二叉搜索树

结束条件为左大于右的情况下
处理的逻辑为为左右节点赋值
这题也是需要思路的，还是要经过事先的演绎进行推导，通过使用二分法，中间节点为根节点

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

func helper(nums []int,left ,right int)*TreeNode{
    if left > right{
        return nil
    }
    var (
        mid = (left + right)/2
        root TreeNode
    )
    root.Val = nums[mid]
    root.Left = helper(nums,left,mid -1)
    root.Right = helper(nums,mid+1,right)
    return &root
}

路径总和

递归法 退出逻辑：当当前节点为的左右节点为空同时当前值==剩余值
处理逻辑 遍历左右节点，分别-根节点值

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil{
        return false
    }
    if root.Left ==nil&& root.Right == nil &&targetSum-root.Val == 0{
        return true
    }
    if  hasPathSum(root.Left,targetSum - root.Val){
        return true
    }
    if  hasPathSum(root.Right,targetSum-root.Val){
        return true
    }
    
    return false
}