leetcode链接
思路:想找到所有的左叶子节点,就要先找到所有的叶子节点,然后把叶子节点中的左叶子节点再找出来,所以递归的一层操作就是:找到叶子节点if not root.left and not root.right: return -1
,然后再看当前节点是否有左孩子并且判断左孩子是不是叶子节点,如果都满足则把这个叶子节点的值添加进num中,然后以同样的逻辑再遍历右孩子。
def sumOfLeftLeaves(root): num = [] def traversal(root): # 判断是叶子节点 if not root.left and not root.right: return -1 # 如果有左孩子并且左孩子是叶子节点(即左叶子节点) if root.left and traversal(root.left)==-1: num.append(root.left.val) # 如果有右孩子 if root.right: traversal(root.right) traversal(root) numsum = sum(num) return numsum
迭代法就更直观了,把当前节点弹出,然后判断他的左孩子是不是左叶子节点,如果是就加上;然后把他的左孩子和右孩子入栈,以同样的逻辑循环即可。
def sumOfLeftLeaves(self, root: TreeNode) -> int: """ Idea: Each time check current node's left node. If current node don't have one, skip it. """ stack = [] if root: stack.append(root) res = 0 while stack: cur_node = stack.pop() # 判断是左叶子节点的逻辑 if cur_node.left and not cur_node.left.left and not cur_node.left.right: res += cur_node.left.val if cur_node.left: stack.append(cur_node.left) if cur_node.right: stack.append(cur_node.right) return res
在函数中再定义函数时,定义数值变量时,存在局部变量还是全局变量的问题。但是如果使用容器来解,就都是全局变量,逻辑上比较清晰。(在递归法中有体现,所以我没定义一个numsum数值变量直接加,而是定义了一个num,然后在最后求和)
灵活运用递归方法。