代码随想录算法训练营第十七天 110.平衡二叉树、257. 二叉树的所有路径、404.左叶子之和

代码随想录算法训练营第十七天 110.平衡二叉树、257. 二叉树的所有路径、404.左叶子之和

110. 平衡二叉树

题目链接：力扣题目链接

文章讲解：代码随想录(https://programmercarl.com)

视频讲解：后序遍历求高度，高度判断是否平衡 | LeetCode：110.平衡二叉树

状态：AC

思路

由之前的104题：求二叉树最大深度一讲，卡哥提到过深度和高度的区别，结合这道题的视频看懂了。举个例子，我们现在站在地上，看见一幢楼会说：“这楼有多高？”；看见一个坑，会说：“这坑有多深？”。也就是说高度要从下往上看、深度要从上往下看。从下向上自然就需要后序遍历。

  1. 每个叶子节点的高度为1，叶子节点的子节点（也就是两个空节点）高度为0；
  2. 定义左子树高度为leftHeight，左子树递归返回左子树的高度，如果高度为-1则执行return -1；
  3. 定义右子树高度为rightHeight，右子树递归返回右子树的高度，如果高度为-1则执行return -1；
  4. 比较左右子树高度差，差的绝对值小于等于1，说明是平衡二叉树，将最高的子树高度加一，回到2、3步继续。否则不为平衡二叉树，return -1。

代码

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
// 平衡二叉树
func isBalanced(root *TreeNode) bool {
	return backTracking(root) != -1
}
// 返回最大值
func maxNum(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func backTracking(root *TreeNode) int {
    // 空节点
	if root == nil {
		return 0
	}
	// left child
	leftHeight := backTracking(root.Left)
	if leftHeight == -1 {
		return -1
	}
	// right child
	rightHeight := backTracking(root.Right)
	if rightHeight == -1 {
		return -1
	}
	// 不是平衡二叉树
	if rightHeight-leftHeight > 1 || rightHeight-leftHeight < -1 {
		return -1
	} else {
		return maxNum(rightHeight, leftHeight) + 1  //高度加一继续返回
	}
}

257. 二叉树的所有路径

题目链接：力扣题目链接

文章讲解：代码随想录(https://programmercarl.com)

视频讲解：递归中带着回溯，你感受到了没？| LeetCode：257. 二叉树的所有路径

状态：AC

思路

回溯算法的比较典型的应用，要输出所有的路径，应该使用先序遍历。走到叶子结点后将路径添加至最后的结果。

卡哥回溯三部曲：

  1. 确立函数参数和返回值：由于是Go语言，全局变量在LeetCode中会出现一些问题，具体可以查看这篇我的这篇博客Go语言刷LeetCode使用全局变量的问题。函数变量包括：
    • 根节点root
    • 这道题的结果result
    • 一条路径path
  2. 确定终止条件：当前节点为子节点时，保存path到result，return
  3. 单次递归：左节点不为空，向左递归；右节点不为空；向右递归

代码

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
37
38
39
func binaryTreePaths(root *TreeNode) []string {
	result := []string{}
	path := []int{}
	getResult(root, &result, &path)
	return result
}

func getResult(root *TreeNode, result *[]string, path *[]int) {
    // 终止条件，并且将切片类型的path按要求写成字符串，添加到result中。
	if root.Left == nil && root.Right == nil {
		*path = append(*path, root.Val) //添加新的节点
		var temp string
		if len(*path) == 1 {
			temp = "1"
		} else {
			temp = strconv.Itoa((*path)[0])
			for i := 1; i < len(*path); i++ {
				temp += "->" + strconv.Itoa((*path)[i])
			}
		}
		*path = (*path)[:len(*path)-1]
		*result = append(*result, temp)
		return
	}
    // 左节点不为空，向左递归
	if root.Left != nil {
		*path = append(*path, root.Val)
		getResult(root.Left, result, path)
		*path = (*path)[:len(*path)-1]
	}
    
    // 右节点不为空，向右递归
	if root.Right != nil {
		*path = append(*path, root.Val)
		getResult(root.Right, result, path)
		*path = (*path)[:len(*path)-1]
	}
}

404.左叶子之和

题目链接：力扣题目链接

文章讲解：代码随想录(https://programmercarl.com)

视频讲解：二叉树的题目中，总有一些规则让你找不到北 | LeetCode：404.左叶子之和

状态：AC

思路

要判断的是所有左叶子的和，选择先序遍历。递归三部曲请出来：

  1. 确立函数参数和返回值：此处没有用全局变量，需要使用一个指针存放和。如何判断是左节点，我这里引入一个变量flag为bool类型。如果向左节点递归，则为true，否则为false。这样当到达叶子节点时候判断flag值就能知道是不是左叶子
    • 根节点root
    • 和指针sum
    • 是否为左节点flag
  2. 确定终止条件：如果是叶子节点，并且flag == true，*sum += root.Val，返回。
  3. 单次递归：如果左节点不为空，向左递归，flag = true；如果右结点不为空，向右递归，flag = false

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func sumOfLeftLeaves(root *TreeNode) int {
	if root.Left == nil && root.Right == nil {
		return 0
	}
	sum := 0
	getSum(root, &sum, false)
	return sum
}

// flag为true, 代表左节点; 否则是右结点
func getSum(root *TreeNode, sum *int, flag bool) { 
	if root.Left == nil && root.Right == nil && flag {
		*sum += root.Val
		return
	}
	if root.Left != nil {
		getSum(root.Left, sum, true)
	}
	if root.Right != nil {
		getSum(root.Right, sum, false)
	}
}