104. 두 갈래 나무의 최대 깊이

Tag Tree DFS
Difficulty Easy
Link https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

분석

깊이 우선 검색을 사용하여 트리의 깊이를 따라 트리의 노드를 훑어봅니다.
첫 번째는 귀속 방법이에요.
귀속 호출의 매개 변수는 창고 공간을 통해 전달되며, 호출 과정에서 라인의 창고 자원을 차지한다
그리고 마지막 끝점 함수까지 가야 순서대로 종료할 수 있습니다. 그 전까지 점용된 창고 공간은 방출되지 않았습니다.
따라서 귀속 호출 횟수가 너무 많아서 창고 자원이 라인의 최대치를 초과하면 넘쳐나고 프로그램이 이상합니다
그래서 두 번째 방법을 사용하려고 합니다.
창고나 대기열을 이용하여 귀속을 비귀속으로 바꾸다

풀다

1. 귀속

/**
 * 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) {
        int ans = dfs(root);
        return ans;
    }
    
    private int dfs(TreeNode root) {
      	//  
        if (root == null) return 0;
        else {
          	//  
            int depth_left = dfs(root.left);
          	//  
            int depth_right = dfs(root.right);
            return Math.max(depth_left, depth_right) + 1;
        }
    }
}

복잡도

시간 복잡도: O(n) O(n) O(n)

공간 복잡도:

최악의 상황: 나무가 완전히 불균형적이다. 예를 들어 각 노드는 왼쪽 노드, O(n) O(n) O(n)만 있다

가장 좋은 상황: 나무가 완전히 균형을 이루고 나무의 높이는 l o g(n) log(n) log(n), 공간의 복잡도는 O(l o g(n) O(log(n) O(log))

2. 비귀속

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
      	//  
        Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
        stack.push(new Pair<>(root, 1));
        int maxDepth = 0;
        while (!stack.isEmpty()) {
            Pair<TreeNode, Integer> pair = stack.pop();
            TreeNode node = pair.getKey();
            maxDepth = Math.max(maxDepth, pair.getValue());
            int currDepth = pair.getValue();
          	//  ， right， left， left 
            if (node.right != null) {
                stack.push(new Pair<>(node.right, currDepth+1));
            }
            if (node.left != null) {
                stack.push(new Pair<>(node.left, currDepth+1));
            }
        }
        return maxDepth;
    }                           
}

복잡도

시간 복잡도: O(n) O(n) O(n)

공간 복잡도: O(n) O(n) O(n)