[代码随想录]Day15-二叉树part04

WtcSky / 2023-08-12 / 原文

题目：110. 平衡二叉树

思路：

就是后序，如果左右差的超过了1，那么就直接返回-1，如果最后收到了-1那一定是false。

代码：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isBalanced(root *TreeNode) bool {
    res := calcIsBalanced(root)
    if res == -1 {
        return false
    }
    return true
}

func calcIsBalanced(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left := calcIsBalanced(root.Left)
    if left == -1 {
        return -1;
    }
    right := calcIsBalanced(root.Right)
    if right == -1 {
        return -1
    }
    if left - right > 1 || right - left > 1 {
        return -1
    }
    r := 1 + max(left,right)
    return r
}

func max(a,b int) int {
    if a > b {
        return a
    }
    return b
}

参考：

代码随想录

题目：257. 二叉树的所有路径

思路：

遇到叶子节点就记录一次结果。

代码：

递归回溯

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var res []string
func binaryTreePaths(root *TreeNode) []string {
    res = []string{}
    travel(root,"")
    return res
}

func travel(root *TreeNode,s string) {
    if root.Left == nil && root.Right == nil {
        tmp := s + strconv.Itoa(root.Val)
        res = append(res, tmp)
        return 
    }
    s += strconv.Itoa(root.Val) + "->"
    if root.Left != nil {
        travel(root.Left,s)
    }
    if root.Right != nil {
        travel(root.Right, s)
    }
    return 
}

参考：

代码随想录

题目：404. 左叶子之和

思路：

当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和右子树左叶子之和，相加便是整个树的左叶子之和。

代码：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumOfLeftLeaves(root *TreeNode) int {
    if root == nil {
        return 0
    }
    leftValue := sumOfLeftLeaves(root.Left)   // 左

    if root.Left != nil && root.Left.Left == nil && root.Left.Right == nil {
        leftValue = root.Left.Val             // 中
    }

    rightValue := sumOfLeftLeaves(root.Right) // 右

    return leftValue + rightValue
}