LeetCode 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.
이 주제의 사고방식:
1. 한 층에 들어갈 때마다 변수(여기는 levelNum)로 현재 루트 노드에서 이 노드까지의 노드 수를 기록한다
2. 잎 노드에 도달하면 현재 최소 깊이를 기록합니다 overall
2. 모든 잎 노드가 한 번에 도달하면 최종 최소 깊이overall를 얻을 수 있다.
class Solution {
public:
	int minDepth(TreeNode *root) {
		if(root == nullptr) return 0;
		int overall = INT_MAX;
		int levelNum = 0;
		minD(root, overall, levelNum);
		return overall;
	}

	void minD(TreeNode *node, int &overall, int levelNum)
	{
		if(node == nullptr) return;
		levelNum++;
		minD(node->left, overall, levelNum);
		minD(node->right, overall, levelNum);
		if(node->left==nullptr && node->right==nullptr)
			overall = min(overall,levelNum);
	}
};
//2014-2-16 update
	int minDepth(TreeNode *root) 
	{
		if (!root) return 0;
		if (!root->left && !root->right) return 1;
		int L = root->left? minDepth(root->left)+1:INT_MAX;
		int R = root->right? minDepth(root->right)+1:INT_MAX;
		return min(L, R);
	}

좋은 웹페이지 즐겨찾기