LeetCode #104 Maximum Depth of Binary Tree 두 갈래 나무의 최대 깊이

Description: 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.
제목 묘사: 두 갈래 나무를 정해 최대 깊이를 찾아낸다.
두 갈래 나무의 깊이는 뿌리 노드에서 가장 먼 잎 노드까지의 가장 긴 경로의 노드 수이다.
설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다.
예: 두 갈래 나무[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

최대 깊이 3을 반환합니다.
사고방식: DFS를 사용하는 주체적 사고방식(깊이 우선 검색)

귀속, 최대 깊이는 좌우 서브 트리의 비교적 큰 값이며, 서브 노드를 귀속할 때마다 +1

교체, 창고를 사용하여 층층이 스캐닝, 새로운 층마다 +1시간 복잡도 O(n), 공간 복잡도 O(n), 그 중에서 n은 나무의 결점수이다. 왜냐하면 모든 결점에 한 번 방문해야 하기 때문이다

DFS(깊이 우선 검색)
깊이 우선 검색 알고리즘(영어: Depth-First-Search, DFS)은 트리나 그림을 훑어보거나 검색하는 데 사용되는 알고리즘으로 트리의 깊이를 따라 트리의 노드를 훑어보고 가능한 한 깊이 있는 검색 트리의 지점이다.노드 v가 있는 모서리가 이미 탐색되었을 때, 검색은 노드 v를 발견한 모서리의 시작 노드로 거슬러 올라갑니다.이 과정은 원본 노드에서 도달할 수 있는 모든 노드를 발견할 때까지 진행되었다.아직 발견되지 않은 노드가 존재한다면 그 중 하나를 원본 노드로 선택하고 상기 과정을 반복합니다. 전체 프로세스는 모든 노드가 접근할 때까지 반복됩니다.무분별한 수색에 속한다.단계:

우선 루트 노드를 창고에 넣고..

창고에서 첫 번째 노드를 꺼내 목표인지 확인합니다.목표를 찾으면 검색을 끝내고 결과를 답장합니다.그렇지 않으면 검증되지 않은 직접 하위 노드를 창고에 넣습니다..

2단계 반복..

감지되지 않은 직접 하위 노드가 없으면이전 레벨 노드를 창고에 넣습니다.2단계 반복..

4단계 반복..

창고가 비어 있으면 전체 그림이 검사되었음을 나타낸다. 즉, 그림에 찾고 싶은 목표가 없다는 것이다.수색을 끝내고'목표를 찾지 못했습니다'라고 답장합니다.

코드: C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 class Solution {
 public:
     int maxDepth(TreeNode* root) {
         if (!root) return 0;
         stack s;
         s.push(root);
         int result = 0;
         while (!s.empty()) {
             int nums = s.size();
             while (nums > 0) {
                 TreeNode* current = s.top();
                 s.pop();
                 if (current -> left) s.push(current -> left);
                 if (current -> right) s.push(current -> right);
                 nums--;
             }
             result++;
         }
         return result;
     }
 };

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1 if root else 0