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.
【代码】