C++LeetCode 구현(104.이 진 트 리 의 최대 깊이)

[LeetCode]104.Maximum Depth of Binary Tree 이 진 트 리 의 최대 깊이
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
    3
/ \
9  20
/  \
15   7
return its depth = 3.
이 진 트 리 의 최대 깊이 문 제 는 깊이 우선 검색 Depth First Search 를 사용 합 니 다.재 귀적 인 완벽 한 응용 은 이 진 트 리 의 최소 깊이 문제 원리 와 같 습 니 다.코드 는 다음 과 같 습 니 다.
C++해법 1:

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};
자바 해법 1:

public class Solution {
    public int maxDepth(TreeNode root) {
        return root == null ? 0 : (1 + Math.max(maxDepth(root.left), maxDepth(root.right)));
    }
}
우 리 는 또한 층 차 를 사용 하여 이 진 트 리 를 옮 겨 다 니 며 총 층 수 를 계산 할 수 있 습 니 다.즉,이 진 트 리 의 최대 깊이 입 니 다.while 순환 중의 for 순환 의 쓰기 에 trick 가 있 습 니 다.반드시 q.size()를 초기 화 에 두 어야 합 니 다.정지 판단 조건 에 두 어 서 는 안 됩 니 다.q 의 크기 는 수시로 변화 하기 때문에 정지 조건 에서 오류 가 발생 할 수 있 습 니 다.코드 는 다음 과 같 습 니 다.
C++해법 2:

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        int res = 0;
        queue<TreeNode*> q{{root}};
        while (!q.empty()) {
            ++res;
            for (int i = q.size(); i > 0; --i) {
                TreeNode *t = q.front(); q.pop();
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
        }
        return res;
    }
};
자바 해법 2:

public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int res = 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            ++res;
            for (int i = q.size(); i > 0; --i) {
                TreeNode t = q.poll();
                if (t.left != null) q.offer(t.left);
                if (t.right != null) q.offer(t.right);
            }
        }
        return res;
    }
}
Github 동기 화 주소:
https://github.com/grandyang/leetcode/issues/104
유사 한 제목:
Balanced Binary Tree
Minimum Depth of Binary Tree
Maximum Depth of N-ary Tree
참고 자료:
https://leetcode.com/problems/maximum-depth-of-binary-tree/
https://leetcode.com/problems/maximum-depth-of-binary-tree/discuss/34207/my-code-of-c-depth-first-search-and-breadth-first-search
C++구현 LeetCode(104.이 진 트 리 의 최대 깊이)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 이 진 트 리 의 최대 깊이 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!

좋은 웹페이지 즐겨찾기