题目：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
}