본문 바로가기
알고리즘

[알고리즘] c++ cpp Minimum Depth of Binary Tree

by keel_im 2020. 10. 22.
반응형

포인트

1. 이진트리의 깊이를 아는 방법, 이진트리는 dfs로 들어간다. 

2. 이진트리는 왼쪽 오른쪽

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

#include <iostream>
using namespace std;

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 == NULL) //루트가 0이면 0
			return 0;
		if (root->left == NULL && root->right == NULL) // Reach leaf node
			return 1;// 왼쪽이 0이고 오른 쪽이 0이면 1
		if (root->left == NULL)
			return minDepth(root->right) + 1; //오른쪽이 1이면 계속 들어간다.(테일 리커전)
		if (root->right == NULL)
			return minDepth(root->left) + 1;
		return min(minDepth(root->left), minDepth(root->right)) + 1;
	}
};

 

반응형

댓글