leetcode: Minimum Depth of Binary Tree

Problem Description:

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 and Precautions:

Way 1: DFS to traverse the whole tree and use a variable to keep the current minimum depth, when encountering a  less deep one (actually the minimum depth variable needs to be updated only when reaching a leaf node), update the minimum depth:

class Solution {
public:
	void dfs(TreeNode *root, int depth, int *pminDepth) {
		if (NULL == root->left && NULL == root->right) 
			*pminDepth = (depth < *pminDepth) ? depth : *pminDepth; 
		if (root->left) dfs(root->left, depth + 1, pminDepth);
		if (root->right) dfs(root->right, depth + 1, pminDepth);
	}

    int minDepthInner2(TreeNode *root) {
		if (NULL == root) return 0;
		int minDepth = INT_MAX;
		dfs(root, 1, &minDepth);  
		return minDepth;
    }

    int minDepth(TreeNode *root) {
		return minDepthInner2(root);
    }
};

Way 2: Try a similar way to get the maximum depth of a binary tree as the following codes show. Note the commented line is a trap which is very easy to fall into. In this problem, we need a path from root to leaf, so if we encouter NULL, it is not necessary a valid path, e.g.,

1
    /
   2

There is only one valid path 1->2. This is the difference.

class Solution {
public:

	int minDepthInner1(TreeNode *root) {
		if (NULL == root)  
			return INT_MAX;  
		if (NULL == root->left && NULL == root->right)
			return 1;  
		return min(minDepthInner1(root->left), minDepthInner1(root->right)) + 1;
	}

    int minDepth(TreeNode *root) {
		// return (NULL == root) ? 0 : min(minDepth(root->left), minDepth(root->right)) + 1;
		if (NULL == root) return 0; 
		return minDepthInner1(root);
    }
};

Tips and Remarks:

(1) Two different solutions reflect two different thinkings: (1) recursive thinking, (2) dfs oriented:
(2) Also note the different way to handle NULL node in the second method, if it is an empty tree, we return 0, for other NULL Nodes, we need to return INT_MAX to indicate there is no valid path!

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on April 20, 2013