笔记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
}
更多推荐
刷题笔记day17
发布评论