Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
입출력 예
Input: root = [3,9,20,null,null,15,7]
Output: 3
우선 본론 부터 말하자면 성공하지 못했다...
내가 생각했던 방법은 아래와 같다.
1. 트리를 만든다
2. 각 leaf노드의 깊이를 탐색한다. push -> []
3. max값을 찾아서 return 한다.
하지만 null일 경우 tree의 left나 right에 넣을 경우엔 root에 있는 null값을 넣고 나서가 문제 였다...
그래서 이런 저런 방법을 시도해봤으나 실패하였다.
뭔가 시도는 했지만 아무것도 못한 코드...
var maxDepth = function(root) {
if(!root.length) return 0;
let tree = new TreeNode(root[0] );
let recursion = (ele){
if(!ele.left){
recursion(ele.left)
}
}
for(let i = 3; i < root.length; i++){
if(tree.left === null){
tree.left = root[i]
}else if(tree.right === null ){
}
}
}
하나 몰랐던 사실이 있었는데, root로 들어오는 값은 트리 자체였다.
그러니까 root = [3,9,20,null,null,15,7]이면 root.left는 [9]였던 것이다. 그러니 우선 tree를 만들 필요가 없었다 ㅎㅎ...
var maxDepth = function(root) {
if (!root) return 0;
const queue = [root];
let depth = 0;
while (queue.length !== 0) {
depth++;
const len = queue.length;
for (let i = 0; i < len; i++) {
if (queue[i].left) queue.push(queue[i].left);
if (queue[i].right) queue.push(queue[i].right);
}
queue.splice(0, len);
}
return depth;
};
이해가 잘 가지 않았지만 하나씩 차근히 생각해 볼 수 있다.
queue | len | depth | queue(push 후) | |
---|---|---|---|---|
1 | [[3,9,20,null,null,15,7]] | 1 | 1 | [[3,9,20,null,null,15,7],[9],[20,15,7]] |
2 | [[[9],[20,15,7]] | 2 | 2 | [[9],[20,15,7],[15],[7]] |
3 | [[15],[7]] | 2 | 3 | [[15],[7]] |
4 | [] |
var maxDepth = function(root) {
if(root === undefined || root===null){
return 0;
}
return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
};