[LeetCode] 111. Minimum Depth of Binary Tree

轉自LeetCode

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.

<Solution>

這題是要算從 root 到最近的 leaf node 的深度

因為是要求最近的 leaf node，會想到使用 BFS 來解

• 一個一個 node 丟到 queue 裡，如果發現了 leaf node，就結束並回傳深度

code 如下

	/**
	* 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) {
	return 0;
	}
	queue<pair<TreeNode *, int>> nodeQue;
	nodeQue.push({root, 1});
	//> BFS
	while(!nodeQue.empty()) {
	//> leaf node
	if(!nodeQue.front().first->left && !nodeQue.front().first->right) {
	break;
	}
	if(nodeQue.front().first->left) {
	nodeQue.push({nodeQue.front().first->left, nodeQue.front().second+1});
	}
	if(nodeQue.front().first->right) {
	nodeQue.push({nodeQue.front().first->right, nodeQue.front().second+1});
	}
	nodeQue.pop();
	}
	return nodeQue.front().second;
	}
	};

view raw binaryTreeMinDepth_1.cpp hosted with ❤ by GitHub

這題其實也可以用 DFS 的想法來解

• 用DFS走到 leaf node，然後回傳每個子樹的最小深度

code 如下 (參考資料)
c++

	/**
	* 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) {
	return 0;
	}
	int left = (root->left == NULL) ? 0 : minDepth(root->left);
	int right = (root->right == NULL) ? 0 : minDepth(root->right);
	return (left == 0 || right == 0) ? left + right + 1 : min(left, right) + 1;
	}
	};

view raw binaryTreeMinDepth_2.cpp hosted with ❤ by GitHub

kotlin

	/**
	* Example:
	* var ti = TreeNode(5)
	* var v = ti.`val`
	* Definition for a binary tree node.
	* class TreeNode(var `val`: Int) {
	* var left: TreeNode? = null
	* var right: TreeNode? = null
	* }
	*/
	class Solution {
	fun minDepth(root: TreeNode?): Int {
	if (root == null) {
	return 0
	}
	val leftHeight = if(root!!.left == null) 0 else minDepth(root!!.left)
	val rightHeight = if(root!!.right == null) 0 else minDepth(root!!.right)
	return if(leftHeight == 0 || rightHeight == 0) {
	leftHeight + rightHeight + 1
	} else {
	Math.min(leftHeight, rightHeight) + 1
	}
	}
	}

view raw minimum_depth_of_bnary_tree.kt hosted with ❤ by GitHub