[LeetCode][JS]Maximum Depth of Binary Tree

문제

문제: https://leetcode.com/explore/challenge/card/december-leetcoding-challenge/569/week-1-december-1st-december-7th/3551/

아래 그림처럼 root배열이 주어지면 그 배열의 이진트리모양의 최대 깊이를 파악하는 문제이다.

위의 그림처럼 이진트리를 배열모양처럼 만들어 놓았다.

function TreeNode(val, left, right) {
     this.val = (val===undefined ? 0 : val)
     this.left = (left===undefined ? null : left)
     this.right = (right===undefined ? null : right)
}

하지만 위의 TreeNode 생성자함수로 객체들이 서로 Linked돼 있는 상태이다.

• JSON.stringify()로 출력해보면 다음과 같은 모양이 나온다.

//[3,9,20,null,null,15,7]
//실제는 아래와 같은 모습이다.
{
  "val":3,
  "left":{"val":9,"left":null,"right":null},
    "right":
    {"val":20,
      "left":{"val":15,"left":null,"right":null},
        "right":{"val":7,"left":null,"right":null}
    }
}

해결방법

1. 이진트리를 순회하면서 종료조건에 그전까지 쌓여왔던 count를 array에 저장한다.
   • left, right로 한칸 씩 들어갈 때마다 arguments의 cnt+1해준다.
   • 재귀를 종료할 때 그때까지 쌓인 cnt를 arr에 넣어준다.
     (arr를 파라미터로 받을 때 배열은 주소 참조하기 때문에 재귀가 끝나고 상위 재귀함수? 로 나와도 arr 역시 push 돼 있는 상태이다.)
2. maxDepth함수에서 array중에서 가장 큰 것을 출력한다.

code

const maxDepth = function(root) {
    const newArr = makeArr(root)
    return Math.max.apply(null,newArr)
};

const makeArr = (root,cnt=0,arr=[]) =>{
    if(!root) {
        arr.push(cnt)
        return arr
    }else{
    makeArr(root.left,cnt+1,arr)
    makeArr(root.right,cnt+1,arr)
    }
    return arr
}