Portfolio

📑 문제

✏️ 풀이

재영

leetCode를 제대로 몰랐던 자의 최후... (tree가 주어졌더라...)


class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }
  enqueue(value) {
    this.queue[this.rear] = value;
    this.rear += 1;
  }
  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return value;
  }
  peek() {
    return this.queue[this.front];
  }
  size() {
    return this.rear - this.front;
  }
  print() {
    console.log(this.queue)
  }
}

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class Tree {
  constructor(node) {
    this.root = node;
  }
  convertTreeObj(arr) {
    if (!arr.length) return;
    const start = arr[0];
    this.root = new Node(start);
    const queue = new Queue();
    queue.enqueue([this.root, 1]);
    while(queue.size()) {
      const [nowNode, nowIndex] = queue.dequeue();
      const leftIndex = nowIndex * 2 - 1;
      const rightIndex = leftIndex + 1;
      if (arr[leftIndex]) { // left;
        nowNode.left = new Node(arr[leftIndex]);
        queue.enqueue([nowNode.left, leftIndex + 1]);
      }
      if (arr[rightIndex]) { // right;
        nowNode.right = new Node(arr[rightIndex]);
        queue.enqueue([nowNode.right, rightIndex + 1]); 
      }
    }
  }
}

const sumOfLeftLeaves = (arr) => {
  const tree = new Tree();
  tree.convertTreeObj(arr);
  return getResult(dfs(tree.root));
}

const dfs = (node, isLeft = false, res = []) => {
  if (!node.left && !node.right) return isLeft ? [node.value] : [];
  return [
      ...res, 
      ...(node.left ? dfs(node.left, true, res) : []), 
      ...(node.right ? dfs(node.right, false, res) : [])
  ];
}

const getResult = arr => arr.reduce((acc,cur) => acc + cur, 0)

const arr = [3,9,20,17,null,15,7];
console.log(sumOfLeftLeaves(arr))

사실상 거의 비슷한 거 같은데, 저의 경우 dfs를 순수 함수로 만드는 걸 좀 더 선호해서, 다음과 같이 leaf들을 모은 배열의 리턴 값이 있게끔(res) 만들어서 나중에 합쳐서 풀었습니다!


const dfs = (node, isLeft = false, res = []) => {
  if (!node.left && !node.right) return isLeft ? [node.val] : [];
  return [
      ...res, 
      ...(node.left ? dfs(node.left, true, res) : []), 
      ...(node.right ? dfs(node.right, false, res) : [])
  ];
}
const sumOfLeftLeaves = root => dfs(root).reduce((acc,cur) => acc + cur, 0)

효성


var sumOfLeftLeaves = function(root) {
    
    let sumOfLeftLeaves = 0;
    
    function dfs(node, isLeft) {
        if(!node) {
            return;
        }
        dfs(node.left, true);
        dfs(node.right, false);
        if(isLeft && !node.left && !node.right) {
            sumOfLeftLeaves += node.val;
        }
    }
    
    dfs(root);
    return sumOfLeftLeaves;
};

재귀함수를 이용해 각 노드를 순회한다.

left 값은 true를 주고, right 값은 false를 주며 순회한다. 만약 node가 null이면 재귀 탈출.

노드가 if문을 충족하면 sum에 val 값을 더함.

은찬


const sumOfLeftLeaves = function(root) {
    let answer = 0;

    const dfs = (node, isLeft) => {
        if(!node.left && !node.right && isLeft){
            answer += node.val;
            return;
        }

        if(node.left){
            dfs(node.left, true);
        }

        if(node.right){
            dfs(node.right, false);
        }
    };
    
    dfs(root, false);
    
    return answer;
};

DFS 문제니 dfs라는 함수를 정의해 활용했습니다.

dfs 함수에는 현재 노드와 현재 노드가 왼쪽 노드인지 알 수 있는 isLeft 변수를 인자로 받습니다.

우선 현재 노드의 자식 노드들(왼쪽과 오른쪽)이 없으며, isLeft가 true인 상태면 answer에 현재 노드의 값을 더합니다.(왼쪽 노드이면서 리프 노드인 상태)

그렇지 않다면 dfs 탐색을 계속 진행합니다.

왼쪽 노드가 있다면 왼쪽 노드를 dfs, 오른쪽 노드가 있다면 오른쪽 노드를 dfs 하면 답이 자동으로 나오게 됩니다.

현석


var sumOfLeftLeaves = function(root) {
    let answer = 0;
    
    function dfs(node) {
				const hasChild = (node) => node.left || node.right

        if(node.left && !hasChild(node.left)) {
            answer += node.left.val
        } 
        
        if(node.left) {
            dfs(node.left)
        }
        
        if(node.right) {
            dfs(node.right)
        }
        return
    }
    dfs(root)
    return answer
};

Sum of Left Leaves

📑 문제

✏️ 풀이