バイナリサーチツリー内のターゲット値に合計するパスを見つける

Question

バイナリサーチツリーとターゲット値を指定すると、ターゲット値まで合計するすべてのパス（複数存在する場合）が検索されます。ツリー内の任意のパスにすることができます。それはルートからである必要はありません。以下のバイナリ検索ツリーの例

：

2 
/\ 
1 3 

合計は6でなければならない場合、パス1 -> 2 -> 3が印刷されるべきです。

Answer 1

ルートからツリーをトラバースし、すべてのパスの合計をポストオーダーで収集します。ハッシュテーブルを使用して、ノードをルートとする可能なパスを格納し、ダウンします。私たちは、それ自身のノードとその子のパスを通るすべてのパスを構築することができます。

ここでは上記を実装した擬似コードですが、実際のパスではなく合計のみを格納します。パス自体については、ハッシュテーブルに終了ノードを格納する必要があります（開始位置はわかりますが、ツリー内の2つのノード間には1つのパスしかありません）。

function findsum(tree, target) 
    # Traverse the children 
    if tree->left 
    findsum(tree.left, target) 
    if tree->right 
    findsum(tree.right, target) 

    # Single node forms a valid path 
    tree.sums = {tree.value} 

    # Add this node to sums of children 
    if tree.left 
    for left_sum in tree.left.sums 
     tree.sums.add(left_sum + tree.value) 
    if tree.right 
    for right_sum in tree.right.sums 
     tree.sums.add(right_sum + tree.value) 

    # Have we formed the sum? 
    if target in tree.sums 
    we have a path 

    # Can we form the sum going through this node and both children? 
    if tree.left and tree.right 
    for left_sum in tree.left.sums 
     if target - left_sum in tree.right.sums 
     we have a path 

    # We no longer need children sums, free their memory 
    if tree.left 
    delete tree.left.sums 
    if tree.right 
    delete tree.right.sums 

これは、ツリーが検索ツリーであるという事実を使用しないため、任意のバイナリツリーに適用できます。

大きなツリーの場合、ハッシュテーブルのサイズは大きくなります。正の値のみがある場合、その合計でインデックスされた配列を使用する方が効率的です。

Answer 2

私の答えはO(n^2)ですが、私はそれが正確であると信じて、少し異なるのアプローチを採用しやすくなります。

ノードiに格納されている値をVALUE[i]とします。私の考えは、各ノードに、rootからそのノードへのパス上の値の合計を格納することです。したがって、ノードごとにi、SUM[i]は、rootからノードiまでのパスの合計です。

各ノードのペア(i,j)に対して、共通の祖先kを見つけます。 SUM(i)+SUM(j)-SUM(k) = TARGET_SUMの場合は、回答が見つかりました。

これはO(n^2)です。すべてのノードペアをループしているからです。しかし、私はすべてのペアを選ぶよりも良い方法を見つけ出すことができます。

サブツリーをルートとするノードのvalueがTARGET_SUMより大きいサブツリーを破棄することで、少し最適化できます。任意の更なる最適化が

擬似コード歓迎:)です：

# Skipping code for storing sum of values from root to each node i in SUM[i] 
for i in nodes: 
    for j in nodes: 
     k = common_ancestor(i,j) 
     if (SUM[i] + SUM[j] - SUM[k] == TARGET_SUM): 
      print_path(i,k,j) 

機能common_ancestor二分探索木のためにかなりの標準的な問題です。 Psuedocode（メモリから、うまくいけばエラーはありません！）：

sub common_ancestor (i, j): 
    parent_i = parent(i) 
    # Go up the parent chain until parent's value is out of the range. 
    # That's a red flag. 
    while(VAL[i] <= VAL[parent_i] <= VAL[j]) : 
    last_parent = parent_i 
    parent_i = parent(i) 
    if (parent_i == NULL): # root node 
     break 
return last_parent 

Answer 3

古い質問が、ここでの私の刺し傷があります - あなたは一度だけ、各ノードを訪問してO（n）の時間でなければなりません：

public static List<ArrayList<Integer>> pathSum(Node head, int sum) { 
    List<Integer> currentPath = new ArrayList<Integer>(); 
    List<ArrayList<Integer>> validPaths = new ArrayList<ArrayList<Integer>>(); 

    dfsSum(head, sum, currentPath, validPaths); 

    return validPaths; 
    } 

    public static void dfsSum(Node head, int sum, List<Integer> currentPath, List<ArrayList<Integer>> validPaths) { 
    if (head == null) return; 

    currentPath.add(head.val); 

    if (head.left == null && head.right == null && sum == head.val) { 
     validPaths.add(new ArrayList<Integer>(currentPath)); 
    } 

    dfsSum(head.left, sum - head.val, new ArrayList<Integer>(currentPath), validPaths); 
    dfsSum(head.right, sum - head.val, new ArrayList<Integer>(currentPath), validPaths); 
    } 

そして、ノードクラス：

class Node { 
    public int val; 
    public Node left; 
    public Node right; 

    public Node(int val) { 
     this.val = val; 
    } 
    }