ノード最短距離(DFS)

説明:
最短パスからエンドノードを求めます.
コード#コード#

public class ShortNodeDFS {
    public static void main(String[] args) {
        Node root = new Node(1);
        root.lt = new Node(2);
        root.rt = new Node(3);
        root.lt.lt = new Node(4);
        root.lt.rt = new Node(4);
        System.out.println(dfs(0, root));
    }

    public static int dfs(int level, Node root){
        if(root.lt==null && root.rt==null) return level;
        return Math.min(dfs(level+1, root.lt), dfs(level+1, root.rt));
    }
}

最短経路を見つける最良の方法はBFSであるが,DFSの使用方法も理解した.しかし,この問題では,ノードは上のコードと同様にしなければならず,エンドノードにサブノードを持つことができないという条件がある.
このコードの中で最も理解しなければならない部分はdfs内部論理そのものである.

if(root.lt==null && root.rt==null) return level;

この部分は、上述した条件に従って、エンドノードに対してサブノードがないため、エンドノードである場合にエンドノードであるか否かを判断すると、そのレベルの条件が返されるからである.
次のコードもあります.

return Math.min(dfs(level+1, root.lt), dfs(level+1, root.rt));

関連コードは重要です.スタックフレームワークの構造を知っていれば、簡単に理解できます.Math.min()でノードの左側サブノードと右側サブノードがエンドノードであることを確認した後、エンドノードであればlevel値を返し、フレームごとに1フレームを返し、最終的に得られた最小値を計算する.
DFSはスタックフレームワークの構造を理解し、常に解放します!