代码随想录算法训练营第十八天|513. 找树左下角的值、112. 路径总和、113. 路径总和 II
【参考链接】
513. 找树左下角的值
【注意】
1.用递归的话就就一直向左遍历，但是到最后一个，它未必是最后一行。是要找到树的最后一行的最左边的值。（不一定是指是左孩子）
2.如果使用递归法，如何判断是最后一行呢，其实就是深度最大的叶子节点一定是最后一行。
3.只要是优先遍历左都可以，所以前中后序都可。
4.层序遍历只需要记录最后一行的第一个节点的数值即可。
【代码】
1.递归遍历中，用一个变量存储最大深度。终止条件：遍历到叶子节点。然后比较当前叶子节点的深度是否比记录最大深度还大，大的话就要更新这个变量。result变量中存储遍历完树最后的最大深度。
2.向左遍历时先判断root.left是否为空，要有回溯过程，要不depth一直在增加，就出现错误。traversal(root.left,depth+1),隐藏回溯的过程在这个递归函数中，depth+1没有改变depth的值。
3.没有中的处理逻辑，只要强调左在右前面就行。
【代码】
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 from collections import deque 8 class Solution(object): 9 def findBottomLeftValue(self, root): 10 """ 11 :type root: TreeNode 12 :rtype: int 13 """ 14 # #1.递归法+回溯 15 # self.max_depth = float('-inf') 16 # self.result = None #最后左下角的值 17 # self.traversal(root,0) #递归 18 19 # return self.result 20 21 # def traversal(self, node, depth): 22 # if not node.left and not node.right:#迭代终止条件：达到叶子节点 23 # if depth > self.max_depth: 24 # self.max_depth = depth 25 # self.result = node.val #因为是先遍历最大深度的左节点所以保证result保存的是左下角的值 26 # return 27 28 # #左 29 # if node.left:#不为空时 30 # depth += 1 31 # self.traversal(node.left, depth) 32 # depth -= 1#回溯 33 # #右 34 # if node.right: 35 # depth += 1 36 # self.traversal(node.right, depth) 37 # depth -= 1 38 39 #2.迭代法：队列 #测试用例[1,2,3,4,null,5,6,null,null,7] 40 queue = deque([root]) 41 while queue: 42 size = len(queue) #1->2->3->1 43 leftmost = queue[0].val #1->2->4->7 44 45 for i in range(size): #1->2->3 46 node = queue.popleft() #1->2->3->4->5->6 47 if node.left: #2->4->5->7 48 queue.append(node.left) #2->34->45->67 49 if node.right: #3->6 50 queue.append(node.right) #23->456 51 if not queue: 52 return leftmost #7
112. 路径总和
【注意】
1.本题前中后序都可以，无所谓，因为中节点也没有处理逻辑。
2.只要找到一条符合的路径就返回，返回true。参数直接传入目标值，做累减，知道叶子节点时为0，就是要求得的路径。
3.终止条件：遇到叶子节点进行判读是否为0.
【代码】
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 hasPathSum(self, root, targetSum): 9 """ 10 :type root: TreeNode 11 :type targetSum: int 12 :rtype: bool 13 """ 14 if not root: 15 return False 16 return self.traversal(root, targetSum) #递归 17 #1.递归+回溯 18 def traversal(self, node, count): 19 # 遇到叶子节点，并且计数为0 20 if not node.left and not node.right and count==0: 21 return True 22 if not node.left and not node.right and count!=0: 23 return False 24 25 #左 26 if node.left: 27 count -= node.left.val 28 if self.traversal(node.right, count): 29 return True 30 count += node.left.val #回溯 31 # 右 32 if node.right: 33 count -= node.right.val 34 if self.traversal(node.right, count): # 递归，处理节点 35 return True 36 count += node.right.val # 回溯，撤销处理结果 37 38 return False
113. 路径总和 II
【代码】
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 __init__(self): 9 self.result = [] 10 self.path = [] 11 #1.递归＋回溯 12 def traversal(self, node, count): 13 if not node.left and not node.right and count == 0: # 遇到了叶子节点且找到了和为sum的路径 14 self.result.append(self.path[:]) 15 return 16 if not node.left and not node.right and count != 0: # 遇到叶子节点而没有找到合适的边，直接返回 17 return 18 #左 19 if node.left: 20 self.path.append(node.left.val) 21 count -= node.left.val 22 self.traversal(node.left, count) 23 count += node.left.val#回溯 24 self.path.pop() 25 26 #右 27 if node.right: 28 self.path.append(node.right.val) 29 count -= node.right.val 30 self.traversal(node.right, count) # 递归 31 count += node.right.val # 回溯 32 self.path.pop() # 回溯 33 34 def pathSum(self, root, targetSum): 35 """ 36 :type root: TreeNode 37 :type targetSum: int 38 :rtype: List[List[int]] 39 """ 40 if not root: 41 return self.result 42 self.path.append(root.val)# 把根节点放进路径 43 self.traversal(root,targetSum-root.val) 44 45 return self.result