110.平衡二叉树

• 递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func getDept(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(getDept(root.Left), getDept(root.Right))  + 1
}
func abs (a int) int {
    if a >= 0 {
        return a
    } 
    return -a
}
func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return isBalanced(root.Left) && 
            isBalanced(root.Right) && 
            abs(getDept(root.Left) - getDept(root.Right)) <= 1
}

257. 二叉树的所有路径

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var res []string
var nodeList []*TreeNode

func readStack() {
    temp := ""
    for i := 0; i < len(nodeList); i++ {
        temp += strconv.Itoa(nodeList[i].Val)
        if i != len(nodeList)-1 {
            temp += "->"
        }
    }
    if temp != "" {
        res = append(res, temp)
    }
}

func dfs(root *TreeNode) {
    if root == nil {
        return
    }
    // visit
    nodeList = append(nodeList, root)
    if root.Left == nil && root.Right == nil {
        readStack()
    }
    dfs(root.Left)
    dfs(root.Right)
    // back
    nodeList = nodeList[:len(nodeList)-1] // 删除最后一个元素
}
func binaryTreePaths(root *TreeNode) []string {
    res = []string{}
    nodeList = []*TreeNode{}
    dfs(root)
    return res
}

404.左叶子之和

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 var sum = 0
 func dfs (root *TreeNode) {
    if root == nil {
        return
    }
    if root.Left != nil {
        if root.Left.Left == nil && root.Left.Right == nil {
            sum += root.Left.Val
        }
        dfs(root.Left)
    }
    dfs(root.Right)
 }
func sumOfLeftLeaves(root *TreeNode) int {
    sum = 0
    dfs(root)
    return sum
}

---

• 分类： 算法
• 标签： 算法基础 二叉树