[leetcode]865.Smallest Subtree with all the Deepest Nodes

leetcode 문제링크

내 깃헙 링크

문제

Given the root of a binary tree, the depth of each node is the shortest distance to the root.

Return the smallest subtree such that it contains all the deepest nodes in the original tree.

A node is called the deepest if it has the largest depth possible among any node in the entire tree.

The subtree of a node is a tree consisting of that node, plus the set of all descendants of that node.

• Example 1:
  - Input: root = [3,5,1,6,2,0,8,null,null,7,4]
  - Output: [2,7,4]
  
• Example 2:
  - Input: root = [1]
  - Output: [1]
  
• Example 3:
  - Input: root = [0,1,3,null,2]
  - Output: [2]

제한사항

The number of nodes in the tree will be in the range [1, 500].
0 <= Node.val <= 500
The values of the nodes in the tree are unique.

해설1

function subtreeWithAllDeepest(root) {
    let index = root;
    
    function getMaxDepth(node, d=0){
        if(!node)return d;
        let left = getMaxDepth(node.left, d+1);
        let right = getMaxDepth(node.right, d+1);
        return Math.max(left, right);
    }
    while(index){
        let left = getMaxDepth(index.left);
        let right= getMaxDepth(index.right);
        if(left>right){
            index=index.left;
        }else if(left<right){
            index= index.right;
        }else{
            return index;
        }
    }
    
};

왼쪽 노드와 오른쪽 노드 중 더 길이가 깊은 것을 선택해서, 선택을 한다. 그리고, 그 노드가 존재 할 때까지 깊게 내려가서, 마지막 값을 출력한다.

추가사항

binary Tree문제에 대해서 풀려면 재귀 함수를 이용하는 법을 숙지하고, 능숙하게 다를 수 있어야 할 것 같다. 특히 깊이를 측정하거나, 값을 측정할 때 있어서 어떤 값을 출력할 것이고, 재귀함수를 통해 어떤 값을 확인할 것인지를 풀이 전에 명확히 정해야 한다.