LeetCode 111. Minimum Depth of Binary Tree

字数统计: 648阅读时长: 4 min

 2021/01/29   Share

111. 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.

Note: A leaf is a node with no children.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 2
Example 2:

Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

Constraints:

The number of nodes in the tree is in the range [0, 105].
-1000 <= Node.val <= 1000

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        if(root->left==nullptr && root->right == nullptr) return 1;
        int min_Set = INT_MAX;
        if(root->left != nullptr) {
            min_Set = min( minDepth(root->left), min_Set );
        }
        if(root->right != nullptr) {
            min_Set = min( minDepth(root->right), min_Set );
        }
        return min_Set + 1;
    }
};

BFS

void BFS(Node start){
  // set queue and visited Set
  Queue<Node> q;
  Set<Node> visited;
  q.offer(start); // put first node into q
  visited.add(start); // add q into set, mark
  int depth = 1;
  
  while(q not empty){
    int q_size = q.size();
    for(int i = 0; i < q_size; i++){
      Node cur = q.poll();
      
      //judge if it is the bottum of q
      if(cur.left == null && cur.right == null){
        return depth;
      }
      // all of cur.adjacent node need to be offered into q
      for(Node x : cur.adj() ) {
        if(x not in visited){
          q.offer(x);
        }
      }
    }
    // after add all of cur.adjacent node, depth++
    depth++;
  }
}

//java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int depth = 1;
        while(!q.isEmpty()){
            int q_size = q.size();

            for(int i = 0; i < q_size; i++){
                TreeNode cur = q.poll();
                if(cur.left == null && cur.right == null) return depth;
                if(cur.left != null){
                    q.offer(cur.left);
                }
                if(cur.right != null){
                    q.offer(cur.right);
                }
            }
            depth++;
        }
        return depth;
    }
}

// Java added visited function (However Binary tree does not need add that)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null ) return 0;

        Queue<TreeNode> q = new LinkedList<>();
      	//Set HashSet
        Set<TreeNode> visited = new HashSet<>();
        q.offer(root);
        visited.add(root);
        int depth = 1;
        while(!q.isEmpty()){
            int q_size = q.size();
            for(int i = 0; i <  q_size; i++){
                TreeNode cur = q.poll();
                if(cur.left == null && cur.right == null) return depth;
                if(cur.left != null){
                    if( !visited.contains(cur.left) ) {
                        q.offer(cur.left);
                        visited.add(cur.left);
                    }
                }
                if(cur.right != null){
                    if( !visited.contains(cur.right) ) {
                        q.offer(cur.right);
                        visited.add(cur.right);
                    }
                }
            }
            depth++;
        }
        return depth;
    }
}

Next Post

Iteratively. 144.Binary Tree Preorder&Inorder Traversal
Previous Post

full permutation with backtracking

CATALOG

1. 111. Minimum Depth of Binary Tree

