[Leetcode]Minimum Depth of Binary Tree

題目：

 

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：設置一個變量存儲當前記錄下的最小深度，采用先序遍歷的方法訪問樹的每一個節點，設置一個變量表示當前節點所在的層次，如果一個節點沒有子節點，那麼就比較該節點的深度與當前的最小深度，選擇兩者之中較小的作為當前的最小深度。

 

代碼：

 

/**
 * 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) {
        int curr_depth=0,min_depth=1000000;
        return PreorderTraverse(root,&curr_depth,min_depth);
    }

private:
    int PreorderTraverse(TreeNode *root, int *curr_depth, int min_depth){
        if(root==nullptr)return 0;
        
        (*curr_depth)++;
        if(root->left!=nullptr){
            min_depth=PreorderTraverse(root->left, curr_depth, min_depth);
        }
        if(root->right!=nullptr){
            min_depth=PreorderTraverse(root->right, curr_depth, min_depth);
        }
        if((root->left==nullptr)&&(root->right==nullptr)){
            min_depth=min(*curr_depth,min_depth);
        }
        
        (*curr_depth)--;
        return min_depth;
    }
};

解題思路2：另一種思路是，當節點為空時，判斷其是否有兄弟節點，如果沒有，那麼令該節點的深度為0，如果有兄弟節點，令該節點的深度為正無窮（INT_MAX）。這樣一來，在上一層節點進行選擇時，將選擇該節點的兄弟節點的深度作為子節點的深度。

 

 

代碼2：

 

/**
 * 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) {
        return minDepth(root,false);
    }

private:
    int minDepth(TreeNode *root, bool hasbrother){
        if(!root){
            return hasbrother==false?0:INT_MAX;
        }
        return 1+min(minDepth(root->left,root->right!=NULL),minDepth(root->right,root->left!=NULL));
    }
};