任务
110.平衡二叉树
给定一个二叉树，判断它是否是 平衡二叉树
思路
典型的树形DP，每个节点向它的左右孩子收集信息，然后利用收集到的信息判断当前节点，最后再将信息传给上层。对于本题，每个节点要判断以自己为根的树是否是平衡二叉树，需要判断3个条件：
- 自己的左子树是否平衡
- 自己的右子树是否平衡
- 自己的左右高度是否相差<=1
只有满足这三个条件，以当前节点为根的二叉树才平衡，返回给上层。
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
height,balanced = self.isNodeBalanced(root)
return balanced
def isNodeBalanced(self,node):
if not node: return 0,True
leftHeight,isLeftB = self.isNodeBalanced(node.left)
rightHeight,isRighttB = self.isNodeBalanced(node.right)
curNodeHeight = max(leftHeight,rightHeight)+1
res = abs(leftHeight - rightHeight) <= 1 and isLeftB and isRighttB
return curNodeHeight,res
257. 二叉树的所有路径
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
思路
采用遍历的思路：
- 对于任意节点，每次首次遍历到节点就将其加入到path中。
- 对于任意节点，递归遍历其左右节点
- 遇到叶子节点后，将之前收集到的路径加入到paths中。
- 从任意节点退出后，需要回溯path。
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
if not root: return []
paths =[]
path = []
self.dfs(path,root,paths)
return paths
#解法1：当前节点退出时，回溯处理，元素出栈
def dfs(self,path,node,paths):
if not node: return
path.append(node.val)
if (not node.left and not node.right):
paths.append('->'.join(map(str,path)))
else:
self.dfs(path,node.left,paths)
self.dfs(path,node.right,paths)
path.pop()
代码随想录与我的思路有些许不同，他的思路是任意节点的子节点返回时回溯，特别的，对于叶子节点，因为左右都为空，所以直接返回。细微之处需要细细体会，代码如下：
#解法2: 当前节点的左右孩子返回时，回溯处理，元素出栈
def dfs(self,path,node,paths):
path.append(node.val) #当前节点加入到路径
if (not node.left and not node.right): # 作为叶子节点的处理
paths.append('->'.join(map(str,path)))
return
else:
if node.left:
self.dfs(path,node.left,paths)
path.pop()
if node.right:
self.dfs(path,node.right,paths)
path.pop() #处理完后当前节点从路径中移除
此外，还可以用隐形回溯，即使用当前层递归函数的局部变量记录路径，从下一层返回时就可以不用显示的调用pop，局部变量就会从之前的函数栈中弹出而保证正确性了。
def dfs(self,node,path,paths):
if not node: return
new_path = path[:] + [node.val]
if not node.left and not node.right:
paathStr = '->'.join(map(str,new_path))
paths.append(paathStr)
self.dfs(node.left,new_path,paths)
self.dfs(node.right,new_path,paths)
404. 左叶子之和
给定二叉树的根节点 root ，返回所有左叶子之和。
思路
由于int类型为不可变类型，所以用成员变量统计sum，也是遍历的思路，递归遍历左右，到达左叶子时处理信息（修改sum)。
class Solution:
def __init__(self):
self.sum = 0
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
self.dfs(root)
return self.sum
def dfs(self,node):
if not node: return 0
self.dfs(node.left)
self.dfs(node.right)
if node.left:
if not node.left.left and not node.left.right: # 左叶子
self.sum += node.left.val
个人觉得代码随想录的方法在理解上比较难,不是很直观，其代码如下：
class Solution:
def sumOfLeftLeaves(self, root):
if root is None:
return 0
if root.left is None and root.right is None:
return 0
leftValue = self.sumOfLeftLeaves(root.left) # 左
if root.left and not root.left.left and not root.left.right: # 左子树是左叶子的情况
leftValue = root.left.val
rightValue = self.sumOfLeftLeaves(root.right) # 右
sum_val = leftValue + rightValue # 中
return sum_val
513.找树左下角的值
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
思路
遍历思路，每次遇到叶子节点，判断其是否是最底层的。
实际编码中，使用depth记录当前节点的深度，使用maxDepth记录最大深度。
由于depth>self.maxDepth,所以每次最底层碰到的第一个节点就会被记录，而同层其他的节点的深度等于该节点，所以不会被更新。
class Solution:
def __init__(self):
self.maxDepth = float('-inf')
self.res = 0
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
self.dfs(root,0)
return self.res
def dfs(self,node,depth):
if not node: return
if not node.left and not node.right: # 叶子节点
if depth > self.maxDepth:
self.maxDepth = depth
self.res = node.val
self.dfs(node.left,depth+1)
self.dfs(node.right,depth+1)
心得体会
更新了对二叉树章节中递归的思考。
- 上节课中树形DP的思路，一般只考虑单层递归逻辑和递归基，如我这个节点和我左右孩子要做什么（局部），我左右子树要做什么（递归）
- 本节的二叉树的所有路径，左叶子之和以及找树左下角的值都是考虑遍历的思路，也就是在思考上，需要去判断我们在遍历过程中需要收集的信息，放入全局变量，然后再考虑单层逻辑，特殊节点逻辑等。特别的，单层逻辑中，需要考虑相对全局变量的回溯，或者利用局部变量隐形回溯。(注：这里的全局变量指的是比当前局部作用域更大的变量，如可变类型的参数，类的成员等）单层逻辑中一般考虑该节点怎么收集，离开该节点时怎么处理。