'Leet Code'수제 1: Minimum Depth of Binary Tree

2915 단어 LeetCodebfs

제목


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을 얻는다.나는 가장 짧은 경로를 구한 이상 분명히 광도 우선 검색이 더욱 효율적이라고 생각한다. 검색된 첫 번째 잎 노드는 틀림없이 뿌리 노드와 가장 가까운 것이다
  • 광도 우선 검색은 현재 노드의 깊이를 어떻게 표시하는지에 대한 문제에 부딪힐 수 있다.내가 채택한 방법은 대기열 levelqueue를 다시 만들어서 각 층의 대기열에 들어가는 노드를 저장하는 것이다. 이렇게 하면 한 층의 반복이 끝난 후에queue를 비워서 모든 층의 반복의 종점을 판단할 수 있다. 각 층의 반복 후 깊이 depth에 1을 더할 수 있다
  • noleft로 표시합니다. noleft가 진짜이고 오른쪽 아이가 없을 때 이 노드는 뿌리 노드에서 가장 가까운 잎 노드입니다. 현재 깊이로 돌아가면 됩니다

  • 코드

    /** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution {
    public:
        int minDepth(TreeNode *root) {
            if (!root) return 0;
            queue<TreeNode*> que;
            queue<TreeNode*> levelq;
            que.push(root);
            int depth=1;
            while(!que.empty()){
                bool first = true;
                bool noleft=false;
                while(!que.empty()){
                    TreeNode* tmp = que.front();
                    que.pop();
                    noleft = false;
                    if (tmp->left)  levelq.push(tmp->left);
                    else{
                        noleft = true;
                    }   
                    if (tmp->right) levelq.push(tmp->right);
                    else{
                        if (noleft){
                            return depth;
                        }
                    }   
                    first = false;
                }
                depth += 1;
                while(!levelq.empty()){
                    que.push(levelq.front());
                    levelq.pop();
                }
            }
        }
    };

    좋은 웹페이지 즐겨찾기