tsanmmmm2000's Tech Blog

Question

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.

Thinking

此題一樣可以用深度優先搜尋法(Depth-first Search)或廣度優先搜尋法(Breadth-first Search)，我們先釐清一下深度(Depth)跟葉子(Leaf)概念，如下圖

如果選擇前者的方法需注意一點，正常情況下，即一節點擁有左右子樹，我們要比較其兩邊的深度，並找出較小的值，這沒有問題；但若一節點只存在其中一子樹，我們無法比較兩邊的深度，因此應該要取該子樹本身的深度，也就是較大的值才對

My C# Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int MinDepth(TreeNode root) {
        if (root == null) return 0;
        var leftDepth = MinDepth(root.left) + 1;
        var rightDepth = MinDepth(root.right) + 1;
        var evaluator = (root.left != null && root.right != null) 
            ? (leftDepth < rightDepth)
            : (leftDepth > rightDepth);
            
        return evaluator ? leftDepth : rightDepth;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int MinDepth(TreeNode root) {
        if (root == null) return 0;
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        var depth = 1;
        while(queue.Count > 0)
        {
            var currentLevelNumber = queue.Count;
            for(var i = 0; i < currentLevelNumber; i++)
            {
                var node = queue.Dequeue();
                if (node.left == null && node.right == null) return depth;
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);                    
            }
            depth++;
        }
        return depth;
    }
}