[leetcode][998] Maximum Binary Tree II

문제 : https://leetcode.com/problems/maximum-binary-tree-ii/

---

이 문제를 해결하려면 먼저 [654] Maximum Binary Tree 문제를 알아야 한다.

654번 문제에서 조건은 배열을 입력받아 최대 값을 가진 노드를 기준으로 왼쪽 subarray는 왼쪽 자식 트리로, 오른쪽 subarray는 오른쪽 자식 트리로 만든다. 즉, 새롭게 추가되는 값은 왼쪽 자식 트리에 들어갈 수 없고, 오른쪽 자식트리에 속하거나 새로운 루트가 되는 경우 2가지 뿐이다.

따라서 알고리즘은, 

1. root가 NULL인 경우 val로 node를 생성해서 반환. (새로운 루트 노드)

2. root의 val보다 입력받은 val이 큰 경우 val로 node를 생성한 후 왼쪽 자식에 루트 노드 연결. 새로 생성한 노드 반환. (새로운 루트 노드)

3. root의 오른쪽 자식을 루트노드로 위 알고리즘 반복 후 반환 한 노드를 root노드의 오른쪽 자식 노드로 갱신. (오른쪽 자식 노드에 추가)

이다. 

---

소스코드 : https://gist.github.com/fpdjsns/902f39da216af4aa2a344dabe0b3e739