企业网站营销常用的方法,wordpress悬浮音乐,网站运营职责,网站建设需求量大404 左叶子之和
给定二叉树的根节点 root #xff0c;返回所有左叶子之和。 示例 1#xff1a; 输入: root [3,9,20,null,null,15,7] 输出: 24 解释: 在这个二叉树中#xff0c;有两个左叶子#xff0c;分别是 9 和 15#xff0c;所以返回 24
思路
迭代法
迭代法理解…404 左叶子之和
给定二叉树的根节点 root 返回所有左叶子之和。 示例 1 输入: root [3,9,20,null,null,15,7] 输出: 24 解释: 在这个二叉树中有两个左叶子分别是 9 和 15所以返回 24
思路
迭代法
迭代法理解起来更容易就是遍历每一个结点去获取左叶子结点的值然后加起来
class TreeNode(object):def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right right# 法一: 迭代法 遍历每一个结点 采用中左右的方式
class Solution(object):def sumOfLeftLeaves(self, root)::type root: TreeNode:rtype: intsum 0 # 最终结果stack [root] # 存储遍历结果while stack:node stack.pop() # 弹出if node.left and (not node.left.left) and (not node.left.right): # 注意判断是否是叶子结点的方式sum node.left.valif node.left:stack.append(node.left)if node.right:stack.append(node.right)return sum递归法
递归法也需要掌握 递归的遍历顺序为后序遍历左右中是因为要通过递归函数的返回值来累加求取左叶子数值之和。 递归三部曲
确定递归函数的参数和返回值
判断一个树的左叶子节点之和那么一定要传入树的根节点递归函数的返回值为数值之和所以为int 使用题目中给出的函数就可以了。
确定终止条件
如果遍历到空节点那么左叶子值一定是0
if not root:return 0注意只有当前遍历的节点是父节点才能判断其子节点是不是左叶子。 所以如果当前遍历的节点是叶子节点那其左叶子也必定是0那么终止条件为
if not root.left and not root.right:return 0 # 这个判断条件也可以不用写确定单层递归的逻辑
当遇到左叶子节点的时候记录数值然后通过递归求取左子树左叶子之和和 右子树左叶子之和相加便是整个树的左叶子之和。单层逻辑 严格按照左中右的顺序
# 左
left_sum self.sumOfLeftLeaves(root.left)
if root.left and (not root.left.left) and (not root.left.right):left_sum root.left.val
# 右
right_sum self.sumOfLeftLeaves(root.right)
sum left_sum right_sum # 中整体递归代码
# 法二: 递归法 遍历方式左右中
class Solution(object):def sumOfLeftLeaves(self, root):if not root:return 0# 左left_sum self.sumOfLeftLeaves(root.left)if root.left and (not root.left.left) and (not root.left.right):left_sum root.left.val# 右right_sum self.sumOfLeftLeaves(root.right)sum left_sum right_sum # 中return sum
