[알고리즘/자바스크립트] 트리에서 잎노드 개수 구하기 (Tree Count Leaves)

Tree Count Leaves

Implement a `countLeaves` in this basic binary Tree class.

 

A leaf node is any node in the tree that has no children. `countLeaves` should

traverse the tree, and return the number of leaf nodes the tree contains.

 

Illustration of a tree with three leaves:

 

Example usage:

var root = new Tree();
root.countLeaves(); // 1
root.addChild(new Tree());
root.countLeaves(); // still 1
root.addChild(new Tree());
root.children[0].addChild(new Tree());
root.children[0].children[0].addChild(new Tree());
root.countLeaves(); // 2

 

var Tree = function () {
  this.children = [];
};

Tree.prototype.countLeaves = function () {
  // Your code here..
  
};

/**
  * add an immediate child
  */
Tree.prototype.addChild = function (child) {
  if (!this.isDescendant(child)) {
    this.children.push(child);
  }else {
    throw new Error("That child is already a child of this tree");
  }

  return this;
};

/**
  * check to see if the provided tree is already a child of this
  * tree __or any of its sub trees__
  */
Tree.prototype.isDescendant = function (child) {
  if (this.children.indexOf(child) !== -1) {
    // `child` is an immediate child of this tree
    return true;
  } else {
    for (var i = 0; i < this.children.length; i++) {
      if (this.children[i].isDescendant(child)) {
        // `child` is descendant of this tree
        return true;
      }
    }
    return false;
  }
};

/**
  * remove an immediate child
  */
Tree.prototype.removeChild = function (child) {
  var index = this.children.indexOf(child);
  if (index !== -1) {
    // remove the child
    this.children.splice(index,1);
  } else {
    throw new Error("That node is not an immediate child of this tree");
  }
};

var root = new Tree();
root.addChild(new Tree());
root.countLeaves();

 

문제는 위와 같고, 위 코드에서 // Your code is here 부분을 채우는 문제이다.

 

처음에 루트 노드를 만들면 children: []을 가지고 있는 객체가 생성되고,

addChild() 메소드와 removeChild로 children 배열에 계속해서 노드를 추가했다 지울 수 있다.

 

자식이 없는 단노드의 개수를 구하는 문제인데,

위 구조에서 단노드의 조건은 children의 length가 0인 노드가 된다.

 

 

 

Tree.prototype.countLeaves = function () {
  // Your code here..
  let count = 0;

  const countLeafNodes = function () {
    if (this.children.length === 0) {
      return count++;
    }
    for (let i = 0; i < this.children.length; i++) {
      countLeafNodes.call(this.children[i]);
    }
  };

  countLeafNodes.call(this);
  return count;
};

 

먼저 count 변수의 초기값을 0으로 설정한다.

 

countLeafNodes라는 함수를 새로 만들었는데, 이 함수는

this.children의 length가 0이면 count 변수를 1 증가시키고 return한다.

 

이제 countLeafNodes를 this 객체를 인자로 주고 call을 이용하여 호출한다.

 

만약에 this.children.length가 0이 아니라면 자식이 있다는 뜻이므로

for문을 돌며 자식 노드를 this값으로 하여 다시 countLeafNodes 함수를 호출한다.

재귀를 돌며 LeafNode를 카운트하다가 작업이 모두 끝나면

count 변수를 리턴한다.

 

 

---

 

Tree.prototype.countLeaves = function () {
  // Your code here..
  if (this.children.length === 0) {
    return 1;
  }

  let count = 0;
  for (let i = 0; i < this.children.length; i++) {
    count += this.children[i].countLeaves();
  }

  return count;
};

 

위 풀이는 함수 안에 또 다른 함수를 만들어서 재귀를 돌리고 있기 때문에

함수를 만들지 않고 푸는 방법으로 다시 풀었다.

 

this.children의 길이가 0이면 1을 리턴한다.

 

만약 this.children의 길이가 0보다 크다면 for문으로 돌려서

children 배열의 요소들을 순회하며 재귀로 countLeaves 함수를 호출한다.

 

호출되는 함수들이 계속 children을 탐색하다가

this.children.length가 0인 단노드를 만나면 1이 리턴될 것이므로,

그 값을 count 변수에 누적한다.