Maximum distinct nodes in a Root to leaf path

문제

Given a Binary Tree, find count of distinct nodes in all the root to leaf paths and print the maximum. 

// left and right can be null if there are no subtree
final case class Tree(value: Int, left: Tree, right: Tree)

 

Examples:

참고: https://www.geeksforgeeks.org/maximum-distinct-nodes-in-a-root-to-leaf-path/

 

풀이 과정

문제에 정의된 Tree 구조에서 상위 ancestor 정보가 각각의 node 마다 있으면 좋겠다.

1. step1 에서 처럼 모든 node 에 각각 ancestor 정보를 List 로 가지도록 한다. 이를 위해 TreeEx class 를 새로 정의한다. 최적화를 위해 ancestor 정보를 추가하는 과정에서 node 의 value 값이 ancestor 에 있을 경우 node 를 null 로 만든다. (해당 node 의 children node 에 ancestor 정보를 추가하는 과정을 생략하기 위해)
2. 그림-C 에서 최하단의 Leaf 만 추출해 size(ancestors) + 1  의 가장 큰 값이 maximun distinct node 의 개수가 된다.

코드

object MaxDistinctPath {
  final case class Tree(value: Int, left: Tree, right: Tree)
  final case class TreeEx(value: Int, ancestors: List[Int], left: TreeEx, right: TreeEx)
  final case class Leaf(value: Int, ancestors: List[Int])

  // 그림-B 과정
  def buildTreeEx(t: Tree, ancestors: List[Int]): TreeEx =
    if (t == null) {
      null
    } else {
      // ancestor 에 동일한 값이 있으면 null node 로 세팅
      if (ancestors.contains(t.value)) {
        null
      } else {
        TreeEx(
          t.value,
          ancestors,
          buildTreeEx(t.left, ancestors :+ t.value),
          buildTreeEx(t.right, ancestors :+ t.value)
        )
      }
    }

  // 그림-C 과정
  def getLeaves(treeEx: TreeEx): List[Leaf] =
    if (treeEx == null) {
      Nil
    } else {
      if (treeEx.left == null && treeEx.right == null) {
        Leaf(treeEx.value, treeEx.ancestors) :: getLeaves(treeEx.left) ::: getLeaves(treeEx.right)
      } else {
        getLeaves(treeEx.left) ::: getLeaves(treeEx.right)
      }
    }

  def solution(tree: Tree): Int = {
    val treeEx: TreeEx    = buildTreeEx(tree, List.empty)
    val leaves: Seq[Leaf] = getLeaves(treeEx)
    val maxLeaf: Leaf     = leaves.sortWith(_.ancestors.size > _.ancestors.size).head
    val maxPath: Seq[Int] = maxLeaf.ancestors :+ maxLeaf.value
    println("nodes:" + maxPath.mkString("-"))
    maxPath.size
  }

  def main(args: Array[String]): Unit = {
    val ex1Tree = Tree(1, Tree(2, Tree(1, null, null), null), Tree(2, Tree(4, null, null), Tree(2, null, null)))
    println(solution(ex1Tree))

    val ex2Tree = Tree(1, Tree(2, Tree(3, null, Tree(2, null, null)), Tree(1, null, null)), null)
    println(solution(ex2Tree))

    val ex3Tree = Tree(
      1,
      Tree(2, Tree(4, null, null), Tree(5, null, null)),
      Tree(3, Tree(6, null, Tree(8, null, null)), Tree(3, null, Tree(9, null, null)))
    )
    println(solution(ex3Tree))
  }
}

 

출력결과

nodes:1-2-4
3
nodes:1-2-3
3
nodes:1-3-6-8
4