LeetCode深さ優先アルゴリズムのツリー(経路関連)

LeetCode深さ優先アルゴリズムのツリー(経路関連)
ツリーの問題は一般的に深さ優先アルゴリズムと広さ優先アルゴリズムによって解決できます.パス関連の問題はDFSまたはDFSに基づいて実現される逆トレースアルゴリズムで実現できます.私たちは次のいくつかの問題を通してDFSと遡及アルゴリズムを復習します.
112.パス総和
説明
二叉樹と一つの目標とを与え、このツリーにルートノードからリーフノードまでの経路があるかどうかを判断する.この経路における全てのノード値の加算は目標和に等しい.
説明: リーフノードとは、サブノードがないノードのことです.
例: 下記の二叉樹と目標とsum=22を与えます.

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

trueを返します.ターゲットと22のルートノードからリーフノードまでの経路5->>4->11->2があるからです.
考え方
まず、テーマは、ルートノードからリーフノードまでの経路、すなわち、どのような状況でリーフノードを巡回しているかを確認する必要があります.葉のノードとは、タイトルによって左右のノードがないノードを意味する.

if (node.left == null && node.right == null)

sumとその判断はノードの総和ですので、これは累積的な和です.各ノードの和を記録し、先にサブノードを巡回する必要があります.このようなシーンがdfsの典型的なシーンです.

addVal();
recursion();

dfsは再帰的に実施することができ、現在はdfsを使用して解決することができ、再帰的な終了の条件は、ノードがnullまたは現在のノードの左右ノードがnullであることが決定されている.もう一つの問題がありますが、どのようにして現在の葉っぱノードの累積値が目標値に等しいかを確認しますか?

if sum == node1.val + node2.val + node3.val;
then
   node3.val = sum - node2.val - node1.val;
 

したがって、サブノードの目標値をsum-curNode.valとして設定し、curNode.val=targetとすると、ルートノードからサブノードまでの経路が存在することと、目標値に等しいことを表す.
コード

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) return sum == root.val;

        return hasPathSum(root.left, sum - root.val) ||
                hasPathSum(root.right, sum - root.val);
    }
}

113.経路総和II
テーマの説明
一本のノードからリーフノードまでの経路の総和が、所与の目標および経路に等しいことを見つけるために、二叉樹と一つの目標とを与えられる.
説明: リーフノードとは、サブノードがないノードのことです.
例:下記の二叉樹と目標と sum=22,

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

戻り値:
[[5,4,11,2],[5,8,4,5]
考え方
この問題は112.パスの合計をもとに変えたものです.変更点はすべてと目標値のパスを記録することです.ですから、この問題は112題のように条件を満たしてから直接bollanタイプに戻るのではなく、条件を満たすまで全てを遍歴して、目標条件を満たしているかどうかを判断する場合、遡及アルゴリズムを使ってこの問題を解決します.
遡っても本質的にはDFSであり、遡って一般的に一つのオブジェクトを使用して記録ノードの値を行い、経路ノードが巡回完了した後、ノードの最後の値が分岐汚染を回避する.
コード

class Solution {
    
    List> res = new ArrayList<>();
    public List> pathSum(TreeNode root, int sum) {
        if (root == null) return res;

        List list = new ArrayList<>();
        this.backTrack(list, root, sum);

        return res;
    }

    void backTrack(List list, TreeNode node, int sum) {
        if (node == null) return ;

        list.add(node.val);
        if (node.left == null && node.right == null) {
            if (node.val == sum) {
                res.add(new ArrayList<>(list));
            }
            
            list.remove(list.size() - 1);
            return;
        }

        backTrack(list, node.left, sum - node.val);
        backTrack(list, node.right, sum - node.val);

        list.remove(list.size() - 1);
    }
}

129.葉ノードの数の和に根を寄せる
テーマの説明
二叉の木を与えられました.その結点は一つずつ預けられます. 0-9 ルートからリーフノードまでの経路は、それぞれ一つの数字を表しています.
例えば、ルートからリーフノードパス1->>2->3は、デジタル123を表す.
ルートから葉っぱノードまで生成されるすべての数字の合計を計算します.
説明: リーフノードとは、サブノードがないノードのことです.
例1:

  : [1,2,3]
    1
   / \
  2   3
  : 25
  :
          1->2      12.
          1->3      13.
  ，     = 12 + 13 = 25.
   2:

  : [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
  : 1026
  :
          4->9->5      495.
          4->9->1      491.
          4->0      40.
  ，     = 495 + 491 + 40 = 1026.

考え方
現象を通して本質を見ます.[1,2,3]この場合、私達が対応する結果は12+13=25です.実際には、まず左のサブツリーの値の合計＋右のサブツリーの合計を記録し、最後に合計値を加算します.

recordValue();
recursion(left);
recursion(right);

後順である以上、実はDFSである.私たちはもう二つの問題があります.第一は現在のノードの値を積算すれば、第二は再帰的な終了条件です.
最初の問題は、実際にはcurVal=preNum*10+node.valで、再帰過程でpreNumのパラメータを記録すればいいです.preNumの初期値は0です.
二つ目の問題は再帰の終了条件です.実は葉っぱのノードを遍歴しています.リーフノード、つまり左ノードと右ノードが空です.
コード

class Solution {
    public int sumNumbers(TreeNode root) {
        if (root == null) return 0;
        
        return dfs(root, 0);
    }
    
    int dfs(TreeNode root, int preNum) {
        if (root == null) return 0;
        
        int num = preNum * 10 + root.val;
        if (root.left == null && root.right == null) return num;
        
        int leftSum = dfs(root.left, num);
        int rightSum = dfs(root.right, num);
        
        return leftSum + rightSum;
    }
}

257.二叉樹の全経路
テーマの説明

       ，                。

  :               。

  :

  :

   1
 /   \
2     3
 \
  5

  : ["1->2->5", "1->3"]

考え方
すべてのパス問題の第一の考えはトレースですが、この問題は特殊な文字列が存在します.要素を削除する時はこのようなシーンを考慮します.だから、ノードを削除する前に現在の文字列のインデックス位置を記録します.これでstingBuider.deleteCharAt(index、cur.length)を使用できます.
コード

class Solution {
    
    List res = new ArrayList<>();
    public List binaryTreePaths(TreeNode root) {
        if (root == null) return res;

        this.backTrack(new StringBuilder(""), root);
        return res;
    }

    public void backTrack(StringBuilder sb, TreeNode node) {
        if (node == null) return;

        if (node.left == null && node.right == null) {
            res.add(sb.toString() + node.val);
            return;            
        }

        int delIndex = sb.length();
        sb.append(node.val).append("->");
        backTrack(sb, node.left);
        backTrack(sb, node.right);

        sb.delete(delIndex, sb.length());
    }
}

プログラマ面接金典04.12シークパス
テーマの説明
一本の二叉樹が与えられており、各ノードは一つの整数値(その値または正または負)を含んでいる.アルゴリズムを設計して、印刷ノードの数値の総和はある所与の値のすべてのパスの数に等しい.なお、経路は必ずしも、二叉樹のルートノードまたはリーフノードから開始または終了しなければならないとは限らないが、その方向は、(親ノードからのみサブノードの方向を指す)下向きでなければならない.
例:下記の二叉樹と目標と sum=22,

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

戻り値:
3解釈:和は22である のパスは[5,4,11,2],[5,8,4,5],[4,11,7]のヒントがあります.
ノード総数<=10000
考え方
この問題は上の問題と違って、ルートは要求されません.ルートから遍歴します.したがって、各階層のノードの値を記録する必要があります.まず、再帰的アルゴリズムによって、ツリーの深さを決定し、現在の深さに基づいて赋価し、現在の深さ対応値を深さが0になるまで遍歴します.
コード

class Solution {

    int res = 0;
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return res;

        int depth = depth(root);
        int[] levels = new int[depth];
        this.bfs(root, levels, 0, sum);

        return res;
    }

    void bfs(TreeNode root, int[] levels, int level, int num) {
        if (root == null) return;

        levels[level] = root.val;
        int sum = 0;
        for (int i = level; i >= 0; i--) {
            sum += levels[i];
            if (sum == num) {
                res += 1;
            }
        }

        bfs(root.left, levels, level + 1, num);
        bfs(root.right, levels, level + 1, num);
    }


    int depth(TreeNode root) {
        if (root == null) return 0;

        int left = depth(root.left);
        int right = depth(root.right);
        
        return left > right ? left + 1 : right + 1;
    }
}