leetcode 알고리즘 연습: 두 갈래 나무의 최대 깊이

제목: 두 갈래 나무를 정해 최대 깊이를 찾아라.
두 갈래 나무의 깊이는 뿌리 노드에서 가장 먼 잎 노드까지의 가장 긴 경로의 노드 수이다.
설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다.
예: 두 갈래 나무[3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7

최대 깊이 3을 반환합니다.사고방식: 변수ld를 설정하고 rd는 먼저 뿌리 노드의 왼쪽에서 출발하여 가장 깊은 잎 노드를 찾습니다. 왼쪽 노드ld+1이 존재하고 오른쪽 노드rd+1이 비교적 큰 값을 되돌려줍니다.오른쪽 동리 마지막으로 최대값 leetcode 코드를 비교합니다.
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


int maxDepth(struct TreeNode* root){
    int ld=0,rd=0;
    if(root)
	{
        ld=maxDepth(root->left)+1;
        rd=maxDepth(root->right)+1;  
    }
    return ld>=rd?ld:rd;
}

leetcode 표준 답안:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int maxDepth(struct TreeNode* root){
    int maxNum = 0;
    int leftNum = 0;
    int rightNum = 0;

    if (root != NULL) {
        maxNum = 1;
    }
    else {
        return maxNum;
    }
    if (root->left != NULL) {
        leftNum = maxDepth(root->left);
    }
    if (root->right != NULL) {
        rightNum = maxDepth(root->right);
    }

    if (leftNum >= rightNum) {
        maxNum += leftNum;
    }
    else {
        maxNum += rightNum;
    }
    return maxNum;
}

좋은 웹페이지 즐겨찾기