문제 설명

• 전형적인 bfs 문제 . 하지만 시간 복잡도가 너무 느리게 나와서 뭐가 문제인지 작성하려고 한다.

나의코드

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if (!root) return []; 
    //root 가 이미 만들어진 binary tree 의 root 임
    let queue=[[root,0]];
    let return_arr=[]
    while(queue.length>0){
        let [first,index]= queue.shift();
        //하나빼고 연관된거 다 넣으면됨
         
         if(!return_arr[index])  return_arr[index]=[first.val];
         else{
              return_arr[index].push(first.val);
         }
       
        if(first.left) queue.push([first.left,index+1]);
        if(first.right) queue.push([first.right,index+1]);
    }

    return return_arr
};

• 완전 하위권... 이정도면 accept 을 잘 안받아준다.
  

남의 코드

var levelOrder = function(root) {
    if (!root) return []
    
    // BFS + queue
    let queue = [root]
    let result = []
    while (queue.length > 0) {
        let level = []
        // l must be set
        let l = queue.length
        for (let i = 0; i < l; i++) {
            node = queue.shift()
            level.push(node.val)
            if (node.left) queue.push(node.left)
            if (node.right) queue.push(node.right)
        }
            
        result.push(level)
    }
    return result
};

Question: let ㅣ= queue.length 의 길이는 유지되는가?

• for 문을 돌기전 이미 선언한 ㅣ 은 queue.push 되어도 길이 변하는 생기지 않는다.
• 또한 첫번쩨 노드의 자식만 돈다고 이미 설정한거와 같은 것

230. Kth Smallest Element in a BST

나의 풀이

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(root, k) {
    //완전 탐색 ㄴㄴ 예전에 배운거 그걸 사용하라는듯
    // 지금 보면 . root 의 오르쪽은 root 보다 큰거 왼쪽은 root 보다 작다.
    // 형태를 변형하지 않는다. + search 으로 작은것을 찾아낸다. 
    // 가장 작은것 부터 찾은다음 차례데로 찾고 k 에 해당하는게 있으면 return 한다. 
    let small=[];
    let answer='';
    function go (go_root,k){
        if(answer!='') return;
        if(!go_root) return ; 
        go(go_root.left,k);
        // 그럼 여기까지 께속가면 제일 작은거 나옴
        if(small.length==k-1){
            answer= go_root.val; 
             small.push(go_root.val);
            return;
        }
        small.push(go_root.val);
        go(go_root.right,k);
    }
    go (root,k);
   return answer;
};