2023年6月22日发(作者：)

Python计算⼆叉树路径总和（遍历、迭代）给你⼆叉树的根节点 root 和⼀个表⽰⽬标和的整数 targetSum ，判断该树中是否存在 根节点到叶⼦节点 的路径，这条路径上所有节点值相加等于⽬标和 targetSum 。叶⼦节点 是指没有⼦节点的节点。⽰例 1：输⼊：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22输出：true⽰例 2：输⼊：root = [1,2,3], targetSum = 5输出：false提⽰：#!/usr/bin/python3# -*- coding: utf-8 -*-class TreeNode(object): def __init__(self, x): = x = None = Nonedef has_path_sum_recursive(tree_node, total): if not tree_node: return False t = total - tree_ if not tree_ and not tree_: return t == 0 return has_path_sum_recursive(tree_, t) or has_path_sum_recursive(tree_, t)def has_path_sum_non_recursive(tree_node, total): if not tree_node: return False # 存放当前节点； node_queue = [tree_node] # 存放当前节点到根节点的路径和； sum_queue = [tree_] while node_queue: current_node, current_sum = node_(0), sum_(0) # 判断当前节点是否是叶⼦节点，如果是，判断能否满⾜路径和为total的条件； if not current_ and not current_: if current_sum == total: return True else: continue # 把当前节点的左右⼦节点（如果存在）及其到根节点的路径和放⼊node_queue和sum_queue； if current_: node_(current_) sum_(current_ + current_sum) if current_: node_(current_) sum_(current_ + current_sum) return Falsen1 = TreeNode(4)n2 = TreeNode(2)n3 = TreeNode(7)n4 = TreeNode(1)n5 = TreeNode(3) = = = = n5print(has_path_sum_non_recursive(n1, 17))