【アルゴリズム学習】二叉木の最小深さminimum-depth-of-binary-tree

二叉木の最小深さ牛客網テスト

一、テーマの説明

与えられたツリーの最小深さを求めます.最小深さとは、ツリーのルートノードから最近のリーフノードまでの最短パス上のノードの数です.Given a binary tree, find its minimum depth.The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

二、考え方の分析

構想1:木の遍歴、遍歴の過程の中で葉のノードと葉のノードのある階層(rootまでいくつかのノードがあればよい)の構想2:木の層序遍歴、層序遍歴の過程の中で葉のノードに出会って結果を得ることができる

三、参考コード

考え方1

public int run(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Map<TreeNode, Integer> map = new HashMap<>();// 
        Map<TreeNode, Integer> map2 = new HashMap<>();// 
        Stack<TreeNode> l3 = new Stack<>();// 
        l3.push(root);
        map.put(root, 0);
        while (l3.size() > 0) {
            TreeNode tempRoot = l3.pop();
            TreeNode left = tempRoot.left;
            TreeNode right = tempRoot.right;
            if (left != null) {
                l3.push(left);
                map.put(left, map.get(tempRoot) + 1);
            }
            if (right != null) {
                l3.push(right);
                map.put(right, map.get(tempRoot) + 1);
            }
            if (left == null && right == null) {
                map2.put(tempRoot, map.get(tempRoot) + 1);
            }
        }
        int min = Integer.MAX_VALUE;
        Set<TreeNode> set = map2.keySet();
        for (TreeNode item : set) {
            if (map2.get(item) < min) {
                min = map2.get(item);
            }
        }
        return min;
    }

考え方2

public int run(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int layer = 1;// 
        Queue<TreeNode> queue = new LinkedTransferQueue<>();// 
        TreeNode layerRightNode = root;
        queue.add(root);
        while (queue.size() > 0) {
            TreeNode tempRoot = queue.remove();
            TreeNode left = tempRoot.left;
            TreeNode right = tempRoot.right;
            if (left != null) {
                queue.add(left);
            }
            if (right != null) {
                queue.add(right);
            }
            if (left == null && right == null) {
                return layer;
            }
            if (layerRightNode == tempRoot) {
                layerRightNode = right == null ? left : right;
                layer++;
            }
        }
        return layer;
    }