LintCode: 두 갈래 나무의 최소 깊이
두 갈래 나무를 정해 최소 깊이를 찾아라.
두 갈래 나무의 최소 깊이는 뿌리 노드에서 가장 가까운 잎 노드까지의 거리다.
두 갈래 나무의 최대 깊이와 달리 단순히 귀속을 사용할 수 없다. 두 갈래 나무의 깊이는 반드시 뿌리 결점에서 잎 결점까지의 거리이기 때문에 좌우 자목의 귀속 결과의 비교적 작은 값을 비교할 수 없다. 왜냐하면 한 아이가 비어 있는 노드에 대해 비어 있는 아이는 0을 되돌려주지만 이 노드는 잎 노드가 아니기 때문에 돌아오는 결과는 잘못된 것이다.
따라서 현재 처리된 노드에 한 아이가 비어 있는 것을 발견하면 최대치 INT_MAX, 결과를 방해하지 않습니다.
/** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */
class Solution {
public:
/** * @param root: The root of binary tree. * @return: An integer */
int minDepth(TreeNode *root) {
// write your code here
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return 1;
int m = minDepth(root->left) + 1;
int n = minDepth(root->right) + 1;
m = (m == 1 ? INT_MAX : m);
n = (n == 1 ? INT_MAX : n);
return m < n ? m : n ;
}
};
참고 자료
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 백엔드에서 데이터를 트리로 변환하고 맵은 json 트리를 생성하여 백엔드로 되돌려줍니다. (백엔드 변환)java 백엔드, 데이터를 트리로 변환하고,map는 json 트리를 생성하여 전방으로 되돌려줍니다(백엔드 변환) 1. 왜 이런 블로그를 쓰나요? 2.java 백엔드 코드 3. 전환된 데이터는 다음과 유사한 형식으로 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
