LeetCode는 매일 한 문제당 111.두 갈래 나무의 최소 깊이

4130 단어

111. 두 갈래 나무의 최소 깊이


Tag Tree DFS
Difficulty Easy
Link https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

분석


두 갈래 나무의 최대 깊이를 구하는 것과 유사하지만 특례[1, 2]의 깊이는 2가 아니라 1이다. 제목은 뿌리 노드에서 잎 노드까지의 가장 짧은 거리를 요구하기 때문이다. 즉, 뿌리 노드의 왼쪽 나무가 비어 있거나 오른쪽 나무가 비어 있을 때 최소 깊이와 최대 깊이가 일치하기 때문이다.

풀다

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        int ans = dfs(root);
        return ans;
    }
    
    private int dfs(TreeNode root) {
        if (root == null) return 0;
        else {
            int depth_left = dfs(root.left);
            int depth_right = dfs(root.right);
          	//  : 
            if (root.left == null || root.right == null) {
                return depth_left + depth_right + 1;
            }
            else {
                return Math.min(depth_left, depth_right) + 1;
            }
        }
    }
    
}

좋은 웹페이지 즐겨찾기