代码随想录算法训练营第十五天 | 513、112、113、106、105

513. 找树左下角的值

package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findBottomLeftValue(root *TreeNode) int {
    queue := []*TreeNode{root}
    result := root.Val
    for len(queue) > 0 {
        levelSize := len(queue)
        currentLeft := queue[0].Val
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        result = currentLeft
    }
    return result
}

112. 路径总和

package main

/**
 * 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 {
        return targetSum == root.Val
    }
    // 递归检查左右子树，更新剩余目标和
    return hasPathSum(root.Left, targetSum-root.Val) || hasPathSum(root.Right, targetSum-root.Val)
}

113. 路径总和 ii

package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, targetSum int) [][]int {
    var result [][]int
    var dfs func(*TreeNode, int, []int)
    dfs = func(node *TreeNode, sum int, path []int) {
        if node == nil {
            return
        }
        sum -= node.Val
        path = append(path, node.Val)
        if node.Left == nil && node.Right == nil {
            if sum == 0 {
                temp := make([]int, len(path))
                copy(temp, path)
                result = append(result, temp)
            }
            return
        }
        dfs(node.Left, sum, path)
        dfs(node.Right, sum, path)
    }
    dfs(root, targetSum, []int{})
    return result
}

106. 从中序与后序遍历序列构造二叉树

package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(inorder []int, postorder []int) *TreeNode {
    indexMap := make(map[int]int)
    for i, v := range inorder {
        indexMap[v] = i
    }
    return helper(inorder, postorder, 0, len(inorder)-1, 0, len(postorder)-1, indexMap)
}

func helper(inorder, postorder []int, inStart, inEnd, postStart, postEnd int, indexMap map[int]int) *TreeNode {
    if postStart > postEnd {
        return nil
    }
    rootVal := postorder[postEnd]
    root := &TreeNode{Val: rootVal}
    inRoot := indexMap[rootVal]
    leftSize := inRoot - inStart
    root.Left = helper(inorder, postorder, inStart, inRoot-1, postStart, postStart+leftSize-1, indexMap)
    root.Right = helper(inorder, postorder, inRoot+1, inEnd, postStart+leftSize, postEnd-1, indexMap)
    return root
}

105. 从前序与中序遍历序列构造二叉树

package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
    indexMap := make(map[int]int)
    for i, v := range inorder {
        indexMap[v] = i
    }
    var helper func(int, int, int, int) *TreeNode
    helper = func(preStart, preEnd, inStart, inEnd int) *TreeNode {
        if preStart > preEnd {
            return nil
        }
        rootVal := preorder[preStart]
        root := &TreeNode{Val: rootVal}
        rootIdx := indexMap[rootVal]
        leftSize := rootIdx - inStart
        root.Left = helper(preStart+1, preStart+leftSize, inStart, rootIdx-1)
        root.Right = helper(preStart+leftSize+1, preEnd, rootIdx+1, inEnd)
        return root
    }
    return helper(0, len(preorder)-1, 0, len(inorder)-1)
}