第六章 二叉树
110.平衡二叉树
平衡二叉树：节点的左右子树的高度差小于1
(1)递归
func isBalanced(root *TreeNode) bool {
if root == nil {
return true
}
depth := 0
getDepth(root, depth)
return abs(getDepth(root.Left, 0) - getDepth(root.Right, 0)) <= 1 && isBalanced(root.Left) && isBalanced(root.Right)
}
func getDepth(root *TreeNode, depth int) int{
if root == nil {
return 0
}
return max(getDepth(root.Left, depth), getDepth(root.Right, depth)) + 1
}
func abs(x int) int {
if x < 0 {
return -1 * x
}else {
return x
}
}
(2)层序
func isBalanced(root *TreeNode) bool {
if root == nil {
return true
}
getDepth(root)
return abs(getDepth(root.Left) - getDepth(root.Right)) <= 1 && isBalanced(root.Left) && isBalanced(root.Right)
}
func getDepth(root *TreeNode) int{
if root == nil {
return 0
}
depth := 0
queue := []*TreeNode{root}
for len(queue) > 0 {
depth++
for _, node := range queue {
queue = queue[1:]
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
}
return depth
}
func abs(x int) int {
if x < 0 {
return -1 * x
}else {
return x
}
}
257.二叉树的所有路径
(1)递归：前序遍历
如果遇到叶子节点，添加路径
路径首先添加节点值，若存在后续节点，添加"->"
func binaryTreePaths(root *TreeNode) []string {
res := []string{}
var help func(root *TreeNode, path string)
help = func (root *TreeNode, path string) {
if root != nil {
path += strconv.Itoa(root.Val)
if root.Left == nil && root.Right == nil {
res = append(res, path)
} else {
path += "->"
help(root.Left, path)
help(root.Right, path)
}
}
}
help(root, "")
return res
}
(2)层序迭代 pathQueue记录根节点到当前节点的path
func binaryTreePaths(root *TreeNode) []string {
res := []string{}
if root == nil {
return res
}
nodeQueue := []*TreeNode{root}
pathQueue := []string{strconv.Itoa(root.Val)}
for i := 0; i < len(nodeQueue); i++ {
node, path := nodeQueue[i], pathQueue[i]
if node.Left == nil && node.Right == nil {
res = append(res, path)
continue
}
if node.Left != nil {
nodeQueue = append(nodeQueue, node.Left)
pathQueue = append(pathQueue, path+"->"+strconv.Itoa(node.Left.Val))
}
if node.Right != nil {
nodeQueue = append(nodeQueue, node.Right)
pathQueue = append(pathQueue, path+"->"+strconv.Itoa(node.Right.Val))
}
}
return res
}
404.左叶子之和
(1)递归
感觉val是包括了二叉树左节点就是叶子节点，和左节点不是叶子节点两种情况，或的关系
func sumOfLeftLeaves(root *TreeNode) int {
if root == nil {
return 0
}
val := 0
if root.Left != nil && root.Left.Left == nil && root.Left.Right == nil {
val = root.Left.Val
}
return val + sumOfLeftLeaves(root.Left) + sumOfLeftLeaves(root.Right)
}
(2)迭代
中序遍历方法
func sumOfLeftLeaves(root *TreeNode) int {
res := 0
if root == nil {
return res
}
stack := []*TreeNode{}
node := root
for len(stack) > 0 || node != nil {
for node != nil {
if node.Left != nil && node.Left.Left == nil && node.Left.Right == nil {
res += node.Left.Val
}
stack = append(stack, node)
node = node.Left
}
node = stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
node = node.Right
}
return res
}
代码随想录文章详解
110.平衡二叉树
257. 二叉树的所有路径
404.左叶子之和
