leetcode Question 55: Minimum Depth of Binary Tree

Minimum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Analysis:

Both DFS and BFS can work for this problem. Since the aim is to find the shortest path, BFS might be a better idea. A queue is used to save every node from the binary tree in depth order. Pop each node, and push its left child and right child (if exist). If the current node is the leaf node (no left and right children), return its depth.  To store the depth of each node, we can use a pair structure <TreeNode* int>.

Note: 

pair<TreeNode*, int> is a good data structure to save the node as well as its depth.

pair constructor  :   (1) pair<TreeNode* int>(node, dep);

                              (2) make_pair(node,dep);

Code(C++):

/**
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        queue< pair<TreeNode*,int> > q;
        int i=0;
        if (!root){return 0;}
        q.push(make_pair(root,1));
        while(!q.empty()){
            pair<TreeNode*,int> cur = q.front();
            q.pop();
            if (!cur.first->left && !cur.first->right){
                return cur.second;
            }
            if(cur.first->left){
                q.push(make_pair(cur.first->left,cur.second+1));
            }
            if(cur.first->right){
                q.push(make_pair(cur.first->right,cur.second+1));
            }
        }
    }
};

Code(Python):

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return an integer
    def maxDepth(self, root):
        if root == None:
            return 0
        q = []
        q.append([root, 1])
        res = 0
        while len(q) != 0:
            node, dep = q.pop()
            res = max(res, dep)
            if node.left != None:
                q.append([node.left, dep + 1])
            if node.right != None:
                q.append([node.right, dep + 1])
        return res