Pythonでルートからリーフまでの数値を合計する
0〜9の数字のみを含む二分木があるとします。ここでは、すべてのルートからリーフへのパスが数値を表す可能性があります。
これは2つのパス21と23を表しているため、出力は21 + 23=44になります。
これを解決するには、次の手順に従います-
- dfs()という再帰関数を1つ作成します。これは、rootとnumを取得します。最初はnum=0
- ノードがnullでない場合
- num:=num *10+ノードの値
- ノードrightがnullでなく、ノードleftがnullでない場合、’
- sum:=sum + num
- num:=num / 10
- 関数から戻る
- dfs(ノードの右側、num)
- dfs(ノードの左側、num)
- num:=num / 10
- メソッドから戻る
- 最初に合計:=0
- rootを使用してdfsを呼び出し、
- 合計を返します。
理解を深めるために、次の実装を見てみましょう-
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def insert(temp,data): que = [] que.append(temp) while (len(que)): temp = que[0] que.pop(0) if (not temp.left): if data is not None: temp.left = TreeNode(data) else: temp.left = TreeNode(0) break else: que.append(temp.left) if (not temp.right): if data is not None: temp.right = TreeNode(data) else: temp.right = TreeNode(0) break else: que.append(temp.right) def make_tree(elements): Tree = TreeNode(elements[0]) for element in elements[1:]: insert(Tree, element) return Tree class Solution(object): def sumNumbers(self, root): self.sum = 0 self.dfs(root) return self.sum def dfs(self,node,num=0): if node: num = num*10 + node.data if not node.right and not node.left: self.sum+=num num/=10 return self.dfs(node.right,num) self.dfs(node.left,num) num/=10 return ob1 = Solution() tree = make_tree([2,1,3]) print(ob1.sumNumbers(tree))
入力
[2,1,3]
出力
44
-
Pythonのルートからリーフへのパスのノードが不十分です
二分木があるとします。このノードと交差するそのようなすべてのルートからリーフへのパスの合計が厳密に制限未満である場合、そのノードは不十分であると呼ばれます。不十分なノードをすべて同時に削除し、結果の二分木のルートを返す必要があります。したがって、ツリーがのようで、制限が1 − の場合、 その場合、出力ツリーは-になります。 これを解決するには、次の手順に従います- メソッドsolve()を定義します。これはルートを取り、制限します ノードに左右のサブツリーがない場合は、 rootの値が1未満の場合はnullを返し、そうでない場合はroot ルートがサブツリーを離れてい
-
Pythonでのパスの合計
1つのツリーと合計があるとします。そのパスをたどると、与えられた合計と一致する合計が得られるように、1つのパスを見つける必要があります。ツリーが[0、-3,9、-10、null、5]のようで、合計が14であるとすると、パス0→9→5があります。 これを解決するために、次の手順に従います。 ルートがnullの場合は、Falseを返します 左右のサブツリーが空の場合、sum – root.val =0の場合はtrueを返し、それ以外の場合はfalseを返します 戻り値solve(root.left、sum – root.val)またはsolve(root.right、su