代码随想录算法训练营|day17

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
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

(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
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

(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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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)
}
1
2
3
4
5
6
7
8
9
10

(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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

代码随想录文章详解

110.平衡二叉树
257. 二叉树的所有路径
404.左叶子之和

总结

平衡二叉树相关