数学とアルゴリズム

[LeetCode]左の葉の合計



Sum Left Leaves



問題

与えられた二分木ですべての左葉の合計を見つけます。
二分木が与えられた場合、そのすべての左葉ノードの値の合計を見つけます。

例：



3 / 9 20 / 15 7 There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

考え

この質問の鍵は、すべての左側の葉ノードを見つける方法です。二分木の場合、すべての左葉ノードを見つけたい場合、私が考える最も直接的な方法は、二分木をトラバースし、アクセスされたノードが左葉ノードであるかどうかを判断して、その値を累積することです。 。

解決策1

私の考えによると、質問は二分木を取得する左リーフノードをどのようにトラバースするかに移ります。そして、二分木をトラバースすると、ツリー自体が再帰的な構造であるため、当然再帰的と考えられます。



二分木の左葉ノードは、その左と右のサブツリーに存在する可能性があります。 2つの部分から、左側の葉ノードについて個別に説明し、それらを追加して目的のノードを取得します。

  • 二分木の左側のサブツリーがリーフノードである場合は、深く掘り下げる必要はありません。探しています。
  • 二分木の左側のサブツリーがリーフノードでない場合、このプロシージャは再帰的に呼び出され、左側のサブツリーの左側のリーフノードの値を取得します。
  • 二分木の右側のサブツリーの場合、リーフノードであるかどうかに関係なく、結果には影響せず、再帰呼び出しは右側のサブツリーの左側のリーフノードの値を直接取得します。

上記の再帰的な考え方によると、コードは次のとおりです。

public int sumOfLeftLeaves(TreeNode root) { If (root == null) return 0//recursive end condition int left, right if (root.left != null && root.left.left == null && root.left.right == null) {//Check if it is a left leaf node left = root.left.val } else { left = sumOfLeftLeaves(root.left) } right = sumOfLeftLeaves(root.right) return left + right }

解決策2

実際、バイナリツリー、プレオーダートラバーサル、インオーダートラバーサル、ポストオーダートラバーサル、階層トラバーサルなどをトラバースする方法は多すぎます。二分木のトラバースは、再帰的または反復的に実行できます。 （言い換えると、ツリーの非再帰的トラバーサルは、書面によるインタビューでよく尋ねられます... = _ =）事前順序のトラバーサルを平均し、値を累積することによって、バイナリツリーをトラバースする次の反復的な方法問題を解決するために左リーフノード。



コードは次のように表示されます。

public int sumOfLeftLeaves(TreeNode root) { TreeNode node = root Stack stack = new Stack() int sum = 0 while (node != null || !stack.isEmpty()) { while (node != null) { stack.push(node) if (node.left != null && node.left.left == null && node.left.right == null) { sum += node.left.val } node = node.left } if (!stack.isEmpty()) { node = stack.pop().right } } return sum }

二分木の非再帰的プレオーダートラバーサルは補助スタックによって実装され、ノードにアクセスするときにそれが左リーフノードであるかどうかを判断するだけで済みます。

以下は、問題を解決するためにバイナリツリーを階層的にトラバースするコードのリストです。

public int sumOfLeftLeaves(TreeNode root) { if (root == null) return 0 Queue queue = new ArrayDeque() int sum = 0 queue.offer(root) while (!queue.isEmpty()) { TreeNode node = queue.poll() if (node.left != null && node.left.left == null && node.left.right == null) { sum += node.left.val } if (node.left != null) queue.offer(node.left) if (node.right != null) queue.offer(node.right) } return sum }

考え方は同じですが、階層トラバーサルはセカンダリキューを介して実装する必要があります。

総括する

実際、この質問は問題の解決策を思い付くのは簡単で、総和問題を二分木を横断する問題に変えます。ここに記録されているのは、主に非再帰的トラバーサルである、バイナリツリーのトラバーサルを確認することでもあります。