Question

Formatted question description: https://leetcode.ca/all/111.html

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, 10⁵].
-1000 <= Node.val <= 1000

Algorithm

DFS

The pitfall is, if a node has a child on the left and a null on the right, how to deal with it. In this case, the node is not a leaf, and we must continue to look for it. This time, we directly judge the root situation. Divided into left and right, or only left and right, return directly.

First, it is judged to be empty. If the current node does not exist, return 0 directly.
Then see if the left child node does not exist, then call the recursive function on the right child node and add 1 to return.
Similarly, if the right child node does not exist, call the recursive function on the left child node and add 1 to return.
If both left and right child nodes exist, call the recursive function on the left and right child nodes respectively, and return the smaller value of the two by adding 1

BFS

BFS traversal, recording the number of layers traversed, once the first leaf node is traversed, the current number of layers is returned, which is the minimum depth of the binary tree, if (!node->left && !node->right) return ans;.

Code

public class Minimum_Depth_of_Binary_Tree {

	/**
	 * Definition for a binary tree node.
	 * public class TreeNode {
	 *     int val;
	 *     TreeNode left;
	 *     TreeNode right;
	 *     TreeNode(int x) { val = x; }
	 * }
	 */

	// @note: key is how to handle null child node
    public class Solution_recursion {

        public int minDepth(TreeNode root) {
            if (root == null) {
                return 0;
            }

            if (root.left == null && root.right == null) {
                return 1; // leaf
            }

            if (root.left == null) {
                return 1 + minDepth(root.right);
            }

            if (root.right == null) {
                return 1 + minDepth(root.left);
            }

            return 1 + Math.min(minDepth(root.left), minDepth(root.right));

        }
    }
}

############

/**
 * 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;
        }
        if (root.left == null) {
            return 1 + minDepth(root.right);
        }
        if (root.right == null) {
            return 1 + minDepth(root.left);
        }
        return 1 + Math.min(minDepth(root.left), minDepth(root.right));
    }
}

// OJ: https://leetcode.com/problems/minimum-depth-of-binary-tree/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        queue<TreeNode*> q;
        q.push(root);
        int ans = 1;
        while (q.size()) {
            int cnt = q.size();
            while (cnt--) {
                auto node = q.front();
                q.pop();
                if (!node->left && !node->right) return ans;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            ++ans;
        }
        return -1;
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        if root.left is None:
            return 1 + self.minDepth(root.right)
        if root.right is None:
            return 1 + self.minDepth(root.left)
        return 1 + min(self.minDepth(root.left), self.minDepth(root.right))

##########

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

class Solution(object):
  def minDepth(self, root):
    """
    :type root: TreeNode
    :rtype: int
    """
    if not root:
      return 0
    left = self.minDepth(root.left)
    right = self.minDepth(root.right)
    if not left and not right:
      return 1
    elif not left:
      return right + 1
    elif not right:
      return left + 1
    else:
      return min(left, right) + 1

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	if root.Left == nil {
		return 1 + minDepth(root.Right)
	}
	if root.Right == nil {
		return 1 + minDepth(root.Left)
	}
	return 1 + min(minDepth(root.Left), minDepth(root.Right))
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function minDepth(root: TreeNode | null): number {
    if (root == null) {
        return 0;
    }
    const { left, right } = root;
    if (left == null) {
        return 1 + minDepth(right);
    }
    if (right == null) {
        return 1 + minDepth(left);
    }
    return 1 + Math.min(minDepth(left), minDepth(right));
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function (root) {
    if (!root) {
        return 0;
    }
    if (!root.left) {
        return 1 + minDepth(root.right);
    }
    if (!root.right) {
        return 1 + minDepth(root.left);
    }
    return 1 + Math.min(minDepth(root.left), minDepth(root.right));
};

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    fn dfs(root: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
        if root.is_none() {
            return 0;
        }
        let node = root.as_ref().unwrap().borrow();
        if node.left.is_none() {
            return 1 + Self::dfs(&node.right);
        }
        if node.right.is_none() {
            return 1 + Self::dfs(&node.left);
        }
        1 + Self::dfs(&node.left).min(Self::dfs(&node.right))
    }

    pub fn min_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        Self::dfs(&root)
    }
}

111 - Minimum Depth of Binary Tree

Question

Algorithm

DFS

BFS

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

DFS

BFS

Code

All Problems

All Solutions