刷题笔记day17

笔记day17"/>

刷题笔记day17

110.平衡二叉树

重点在如果左右不平衡的情况下，就一直返回-1，其他的情况就正常的计算左右节点高度的最大值 + 1，就是树的高度了。

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func isBalanced(root *TreeNode) bool {// 使用递归的方法，if dg(root) != -1 {return true} else {return false}
}func dg(root *TreeNode) int {if root == nil {return 0}leftH := dg(root.Left)if leftH == -1 {return -1}rightH := dg(root.Right)if rightH == -1 {return -1}if absSub(leftH, rightH) > 1 {return -1}return max(leftH, rightH) + 1
}func absSub(a, b int) int {if a - b > 0 {return a - b} else {return b - a}
}func max(a, b int) int {if a > b {return a} else {return b}
}

257. 二叉树的所有路径

采用前序遍历，迭代法。

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
import ("container/list""strconv"// "fmt"
)func binaryTreePaths(root *TreeNode) []string {// 思路：使用，// 迭代，前序遍历var result []stringif root == nil {return result}stack := list.New()stack.PushBack(root)path := list.New()path.PushBack(toString(root.Val))for stack.Len() > 0 {// 取出栈顶元素top := stack.Remove(stack.Back())node := top.(*TreeNode)// 取出 path 栈顶元素top2 := path.Remove(path.Back())p1 := top2.(string)// 叶子结点，打印路径if node.Right == nil && node.Left == nil {result = append(result, p1)}if node.Right != nil {stack.PushBack(node.Right)// path的栈顶都是已经走过的道路，仅需要加上当前的值既可。path.PushBack(p1 + "->" + toString(node.Right.Val))}if node.Left != nil {stack.PushBack(node.Left)path.PushBack(p1 + "->" + toString(node.Left.Val))}}return result
}func toString(a int) string {return strconv.Itoa(a)
}

404. 左叶子之和

使用递归的方法，只需要判断是不是从左节点下来，且是叶子结点既可。不是则返回0。最后做一个累加。

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func sumOfLeftLeaves(root *TreeNode) int {// 思路，前序遍历，只需要记录是不是左叶子既可（通过参数）// 迭代的方法return traversal(root, false)
}func traversal(root *TreeNode, isLeft bool) int {if root == nil {return 0}if isLeft && root.Left == nil && root.Right == nil {return root.Val}leftValue := traversal(root.Left, true)rightValue := traversal(root.Right, false)return leftValue + rightValue
}