두 갈래 나무 뿌리 결점에서 잎 노드까지의 가장 짧은 거리

두 갈래 나무를 정해서 그것의 최소 깊이를 찾아라.최소 깊이는 뿌리 노드에서 가장 가까운 잎 노드까지의 가장 짧은 경로를 따라 노드의 수입니다.

사고방식1: 귀착.

노드의 좌우 트리가null일 때 0

으로 되돌아오기

왼쪽 트리가null이면 오른쪽 트리로 돌아가기 +1;

오른쪽 글자가null이면 왼쪽 트리로 되돌아오기 +1;

좌우 트리가 비어 있지 않으면 좌우 트리의 귀속 최소값을 되돌려줍니다.

public class Solution {
    public int run(TreeNode root) {
     // null ， 0
        if(root==null)
            return 0;
            // null， +1；
        if(root.left==null)
           return run(root.right)+1;
           // null， +1；
        if(root.right==null)
           return run(root.left)+1;
           // ， 。
        int right=run(root.right)+1;
        int left=run(root.left)+1;
        return left>right?right:left;
    }
}

사고방식2: 비귀속 차원 두루

하나의 대기열로 데이터를 저장

각 층 노드를 훑어보고 순환할 수 있으며 훑어본 후 깊이가 1.

좌우 트리가null일 때depth

로 되돌아오기

import java.util.*;
public class Solution {
    public int run(TreeNode root) {
        Queue queue=new LinkedList<>();
        if(root==null)
            return 0;
        queue.add(root);
        int depth=1;
        while(!queue.isEmpty()){
            int len=queue.size();
            // 
            while(len>0){
                TreeNode tree=queue.poll();
                if(tree.left==null && tree.right==null)
                    return depth;
                if(tree.left!=null)
                    queue.add(tree.left);
                if(tree.right!=null)
                    queue.add(tree.right);
                len--;
            }
            depth++;
        }
        return depth;
    }
}