【代码随想录】算法训练计划17

1、 110.平衡二叉树

题目：
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

思路：

• 经典后序遍历，感觉所有的后序遍历的二叉树都一样了
• 因为要返回高度，所以新建一个dfs
• go 没有abs函数？

func isBalanced(root *TreeNode) bool {return hou(root) != -1
}
func hou(node *TreeNode) int {if node == nil {return 0}leftHigh := hou(node.Left)if leftHigh == -1 {return -1}rightHigh := hou(node.Right)if rightHigh == -1 {return -1}if leftHigh-rightHigh > 1 || rightHigh-leftHigh > 1 {return -1}return 1+max(leftHigh, rightHigh)
}
func max(a,b int) int {if a>b {return a}; return b}

2、257. 二叉树的所有路径

题目：
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。

思路：

• 叶子节点特性，就是判断条件，就是左右为空
• 条件判断
• 注意 res 的声明与初始化

var res []string 
func binaryTreePaths(root *TreeNode) []string {res = []string{}path(root, "")return res
}
func path(node *TreeNode, list string)  {if node == nil {return }list += strconv.Itoa(node.Val)// 想清楚逻辑if node.Left == nil && node.Right == nil {res = append(res, list)} else {list += "->"path(node.Left, list)path(node.Right, list)}
}

3、404. 左叶子之和

题目：
给定二叉树的根节点 root ，返回所有左叶子之和。

思路：

• 后序，左右中
• 重点就是判断规则
• 规则就是左节点之后处理一下是否拿这个节点的值！！！

func sumOfLeftLeaves(root *TreeNode) int {if root == nil {return 0}if root.Left == nil && root.Right == nil {return 0}// 叶子节点leftNumber := sumOfLeftLeaves(root.Left)if root.Left != nil && root.Left.Left==nil && root.Left.Right==nil {leftNumber = root.Left.Val}rightNumber := sumOfLeftLeaves(root.Right) // right就算是叶子节点，也不需要返回值// 这个条件怎么搞？return leftNumber+rightNumber
}