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

【参考链接】

110. 平衡二叉树

【注意】

1.一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

2.求高度一定要用后序遍历。

【代码】

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, val=0, left=None, right=None):
 4 #         self.val = val
 5 #         self.left = left
 6 #         self.right = right
 7 class Solution(object):
 8     def isBalanced(self, root):
 9         """
10         :type root: TreeNode
11         :rtype: bool
12         """
13         if self.get_height(root) != -1:
14             return True
15         else:
16             return False
17     
18     def get_height(self,root):
19         if not root:
20             return 0
21         
22         #左子树不是平衡二叉树直接返回-1
23         left_height = self.get_height(root.left)
24         if left_height == -1:
25             return -1
26         #右子树不是平衡二叉树直接返回-1
27         right_height = self.get_height(root.right)
28         if right_height == -1:
29             return -1
30         #中
31         if abs(left_height - right_height) > 1:
32             return -1
33         else:
34             return 1 + max(left_height,right_height)   

257. 二叉树的所有路径

【注意】

1.给定一个二叉树，返回所有从根节点到叶子节点的路径。

2.一定要使用前序遍历。

3.一个参数数组记录单条路径，一个数组记录所有路径。

4.在这道题目中将第一次涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一个路径再进入另一个路径。

5.回溯和递归是一一对应的，有一个递归，就要有一个回溯。

6.回溯的本质是在回头的时候把状态改回来。

【代码】

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, val=0, left=None, right=None):
 4 #         self.val = val
 5 #         self.left = left
 6 #         self.right = right
 7 import copy
 8 
 9 class Solution(object):
10     def binaryTreePaths(self, root):
11         """
12         :type root: TreeNode
13         :rtype: List[str]
14         """
15         if not root:
16             return []
17         result = []
18         self.generate_paths(root, [], result)
19         return result
20     #递归＋回溯（前序遍历：中左右）
21     def generate_paths(self, node, path, result):
22         #中，将节点值加入path中
23         path.append(node.val)
24         #如果最后一个节点是叶子节点，则将一条路径加入到result中，
25         if not node.left and not node.right:
26             #map(str, path) 将path列表中的所有元素转换为字符串类型，然后使用 “->” 符号进行连接，结果是一个字符串。
27             result.append('->'.join(map(str, path)))
28         #左，不为空时，遍历左子树时需要注意将当前路径的副本进行传递，以避免影响右子树的遍历。
29         if node.left:
30             self.generate_paths(node.left, copy.copy(path), result)
31         #右，不为空时
32         if node.right:
33             self.generate_paths(node.right, copy.copy(path), result)
34         #遍历完左子树和右子树后，我们需要将 path 列表中的最后一个元素弹出，以便回溯到它的父节点。
35         path.pop()

ps：还差一题，