Re: [閒聊] 每日LeetCode

[Rushia (みけねこ的鼻屎)]

https://leetcode.com/problems/minimum-depth-of-binary-tree/description/
111. Minimum Depth of Binary Tree
給你一個二元樹，返回他的最小深度，最小深度為 root 節點到葉子節點的最小距離。

Example 1:
https://assets.leetcode.com/uploads/2020/10/12/ex_depth.jpg
Input: root = [3,9,20,null,null,15,7]
Output: 2

Example 2:
Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

思路：
1.用廣度優先去traversal二元樹，如果某個節點的左右兩個子節點都為空，表示找到
  最小深度。

Java Code：
-------------------------------------------
class Solution {
    public int minDepth(TreeNode root) {
        int depth = 0;
        if (root == null) {
            return depth;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                if (curr.left == null && curr.right == null) {
                    return depth;
                }
                if (curr.left != null) {
                    queue.offer(curr.left);
                }
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
            }
        }

        return depth;
    }
}
-------------------------------------------

--
https://i.imgur.com/YPBHGGE.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1688990744.A.274.html
→ a9486l: 大師
→ ririoshi: 大師