天天看點

LeetCode 111 Minimum Depth of Binary TreeLeetCode 111

LeetCode 111

Minimum Depth of Binary Tree

  • Problem Description:

    給出一棵二叉樹,輸出二叉樹中從根節點到最近葉節點所經過的節點數。

    具體的題目資訊:

    https://leetcode.com/problems/minimum-depth-of-binary-tree/description/

  • Example:
    LeetCode 111 Minimum Depth of Binary TreeLeetCode 111
  • Solution:
    • 解題思路:

      通過二叉樹的層次周遊實作,當周遊過程中發現第一個葉節點(即距離根節點最近的葉節點),輸出目前的層數即可。

    • 程式設計實作:
/**
 * Definition for a binary tree node.
 * 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 == NULL) return ;
        if (root->left == NULL&&root->right == NULL) return ;
        TreeNode* node[];
        int front = -, rear = -;
        int last = , level = , flag = ;
        node[++rear] = root;
        while(front<rear) {
            TreeNode* temp = node[++front];
            if (temp->left == NULL&&temp->right == NULL) {
                level++;
                break;
            }
            if (temp->left) {
                node[++rear] = temp->left;
            }
            if (temp->right) {
                node[++rear] = temp->right;
            }
            if (front == last) {
                level++;
                last = rear;
            }
        }
        return level;
    }
};