【スナップアルゴリズム】112-パス合計

タイトル
ツリーとターゲット和を指定し、ツリーにルートノードからリーフノードへのパスが存在するかどうかを判断します.このパスのすべてのノード値がターゲット和に加算されます.
説明:リーフノードとは、サブノードがないノードを指します.
例:次のツリーとターゲットとsum=22が与えられます.

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

ターゲットと22のルートノードからリーフノードへのパス5->4->11->2があるため、trueを返します.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/path-sum著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
問題解
ツリー定義
まず、ツリーの構造TreeNodeを定義します.

/* Definition for a binary tree node. */
public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;

  TreeNode(int x) {
    val = x;
  }
}

方法1:再帰
最も直接的な方法は、再帰を利用して、ツリー全体を巡回することです.現在のノードが葉でない場合、そのすべての子供ノードに対してhasPathSum関数を再帰的に呼び出し、sum値から現在のノードの重み値を減算します.現在のノードがリーフである場合、sum値が0であるかどうか、すなわち所与のターゲットとが見つかっているかどうかを確認します.

class Solution {
  public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null)
      return false;

    sum -= root.val;
    if ((root.left == null) && (root.right == null))
      return (sum == 0);
    return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
  }
}

複雑度分析
時間複雑度:各ノードに1回アクセスし,時間複雑度はO(N)O(N)O(N)であり,ここでN Nはノード個数である.空間複雑度:最悪の場合、ツリー全体が非平衡であり、例えば各ノードに子供が1人しかいない場合、再帰的にはN N N回(ツリーの高さ)が呼び出されるため、スタックの空間オーバーヘッドはO(N)O(N)O(N)O(N)である.しかし、最良の場合、木は完全にバランスがとれており、高さはlog(N)log(N)log(N)log(N)だけであるため、この場合の空間複雑度はO(log(N))O(log(N))O(log(N))のみである.
方法2:反復
アルゴリズム#アルゴリズム#
スタックで再帰を反復形式に変換できます.深度優先検索は、最悪の場合を除いて、広さ優先検索よりも高速です.最悪の場合、ターゲット和を満たすroot->leafパスが最後に考慮される場合、深さ優先探索と広さ優先探索の代価は共通する.
深度優先ポリシーを使用して各ノードにアクセスし、残りのターゲットとを更新します.
ルートノードを含むスタックからシミュレーションを開始し、残りのターゲットはsum-rootである.val.
次に反復を開始します:現在の要素がポップアップされ、現在の残りのターゲットが0の場合、リーフノードでTrueが返されます.残りの和がゼロでなく、非リーフノードにある場合、現在のノードのすべての子供と対応する残りの和をスタックに押し込みます.

class Solution {
  public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null)
      return false;

    LinkedList<TreeNode> node_stack = new LinkedList();
    LinkedList<Integer> sum_stack = new LinkedList();
    node_stack.add(root);
    sum_stack.add(sum - root.val);
    
    TreeNode node;
    int curr_sum;
    while ( !node_stack.isEmpty() ) {
      node = node_stack.pollLast();
      curr_sum = sum_stack.pollLast();
      if ((node.right == null) && (node.left == null) && (curr_sum == 0))
        return true;
    
      if (node.right != null) {
        node_stack.add(node.right);
        sum_stack.add(curr_sum - node.right.val);
      }
      if (node.left != null) {
        node_stack.add(node.left);
        sum_stack.add(curr_sum - node.left.val);
      }
    }
    return false;
  }
}

複雑度分析
時間複雑度:再帰法と同様にO(N)O(N)O(N)である.空間的複雑さ:木のアンバランスが最悪の場合はO(N)O(N)O(N)である.最良の場合(木がバランスしている)はO(log⁡N)O(log N)O(logN)である.
作者:LeetCodeリンク:https://leetcode-cn.com/problems/two-sum/solution/lu-jing-zong-he-by-leetcode/出典:力扣(LeetCode)著作権は作者の所有.商业転載は作者に连络して授権を得て、非商业転載は出典を明記してください.
感想
さいきかいほう
実行時間:1 ms、すべてのJavaコミットで98.40%のユーザーを破った
メモリ消費量:37.3 MB、すべてのJavaコミットで66.08%のユーザーを破った

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root==null) return false;
        if(root.left==null&&root.right==null) return root.val==sum;
        if(root.left==null) return hasPathSum(root.right, sum-root.val);
        else if(root.right==null) return hasPathSum(root.left,sum-root.val);
        else return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right, sum-root.val);
    }
}