代码随想录算法训练营第十四天 | 110、257、404、222

110. 平衡二叉树

package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isBalanced(root *TreeNode) bool {
    return getHeight(root) != -1
}

func getHeight(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left := getHeight(root.Left)
    if left == -1 {
        return -1
    }
    right := getHeight(root.Right)
    if right == -1 {
        return -1
    }
    // 检查高度差是否超过 1
    if left-right > 1 || right-left > 1 {
        return -1
    }
    // 返回当前子树的最大深度
    if left > right {
        return left + 1
    }
    return right + 1
}

257. 二叉树的所有路径

package main

import (
    "strconv"
    "strings"
)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func binaryTreePaths(root *TreeNode) []string {
    var result []string
    if root == nil {
        return result
    }
    traverse(root, []string{}, &result)
    return result
}

func traverse(node *TreeNode, path []string, result *[]string) {
    // 将当前节点值加入路径
    path = append(path, strconv.Itoa(node.Val))

    // 叶子节点：生成路径字符串
    if node.Left == nil && node.Right == nil {
        *result = append(*result, strings.Join(path, "->"))
        return
    }

    // 递归处理左右子树（注意传入拷贝的新路径）
    if node.Left != nil {
        traverse(node.Left, append([]string{}, path...), result)
    }
    if node.Right != nil {
        traverse(node.Right, append([]string{}, path...), result)
    }
}

404. 左叶子之和

package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumOfLeftLeaves(root *TreeNode) int {
    sum := 0
    helper(root, false, &sum)
    return sum
}

func helper(node *TreeNode, isLeft bool, sum *int) {
    if node == nil {
        return
    }
    // 当前节点是左叶子时累加
    if isLeft && node.Left == nil && node.Right == nil {
        *sum += node.Val
        return
    }
    // 递归处理左右子树，标记左子树为 true
    helper(node.Left, true, sum)
    helper(node.Right, false, sum)
}

222. 完全二叉树的节点个数

package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left := leftDepth(root.Left)
    right := rightDepth(root.Right)
    if left == right {
        return (1 << (left + 1)) - 1
    }
    return 1 + countNodes(root.Left) + countNodes(root.Right)
}

func leftDepth(node *TreeNode) int {
    depth := 0
    for node != nil {
        depth++
        node = node.Left
    }
    return depth
}

func rightDepth(node *TreeNode) int {
    depth := 0
    for node != nil {
        depth++
        node = node.Right
    }
    return depth
}