Leetcode 655: 출력 이 진 트 리

m * n 의 2 차원 문자열 배열 에 이 진 트 리 를 출력 하고 다음 규칙 을 준수 합 니 다.
행수 m 이 진 트 리 의 높이 를 정 하 는 것 과 같 아야 합 니 다.열수 n 항상 홀수 여야 한다.루트 노드 의 값 (문자열 형식 으로 표시) 은 놓 을 수 있 는 첫 줄 의 한가운데 에 놓 아야 합 니 다.루트 노드 가 있 는 줄 과 열 은 남 은 공간 을 두 부분 (왼쪽 아래 부분 과 오른쪽 아래 부분) 으로 나 눌 것 입 니 다.왼쪽 아래 에 왼쪽 트 리 를 출력 하고 오른쪽 트 리 를 오른쪽 아래 에 출력 해 야 합 니 다.왼쪽 아래 와 오른쪽 아래 부분 은 같은 크기 가 있어 야 한다.비록 한 개의 나무 가 비어 있 고 다른 한 개의 나무 가 비어 있 지 않 더 라 도, 너 는 빈 나무 에 어떤 것 도 출력 할 필요 가 없 지만, 다른 나무 에 충분 한 공간 을 남 겨 두 어야 한다.그러나 두 개의 나무 가 모두 비어 있다 면 어떤 공간 도 남 겨 둘 필요 가 없다.사용 하지 않 은 공간 마다 빈 문자열 '' 을 포함 해 야 합 니 다.같은 규칙 으로 하위 트 리 를 출력 합 니 다.
예시 1:
입력:     1     /    2 출력: ["," 1 ","], ["2", ","] 예시 2:
입력:     1     / \    2   3     \      4 출력: [",", ",", ",", ",", ",", "], ["", "2", "", "", "", "3", ""],  [",", "," 4 ",", ",", ","] 예시 3:
입력:      1      / \     2   5    /    3   /  4  출력: [", "",  "", "",  "", "", "", "1", "",  "",  "",  "",  "", "", ""]  ["",  "",  "", "2", "", "", "", "",  "",  "",  "",  "5", "", "", ""]  ["",  "3", "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]  ["4", "",  "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]]
사고: 제목 의 예 를 통 해 알 수 있 듯 이 출력 2 차원 배열 의 줄 수 m 는 이 진 트 리 의 깊이 이 고 출력 2 차원 배열 의 너비 n = 2 ^ m - 1 이다.출력 된 전체 2 차원 배열 은 줄 가운데 에 있 는 이 진 트 리 의 뿌리 이 고 왼쪽 은 왼쪽 나무 이 며 오른쪽 은 오른쪽 나무 입 니 다.이러한 규칙 에 따라 우 리 는 재 귀적 인 방법 으로 차례대로 데 이 터 를 이 2 차원 배열 에 삽입 할 수 있다.
다음은 코드 구현:

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};


class Solution {
public:
    vector> printTree(TreeNode* root)
     {
        int m = treeHeight(root);
	    int n = pow(2, m) - 1;
	
	    vector> res(m, vector(n, ""));
	    insertPrint(root, res, 0, 0, n - 1);
	    return res;
     }

    void insertPrint(TreeNode* root, vector>& res, int row,int left, int right)   
    {
	    if (root == NULL || (start > end)) return;
	    int mid = (left + right) /2;
	    res[row][mid] = to_string(root->val);
	    insertPrint(root->left, res, row + 1, left, mid);
	    insertPrint(root->right, res, row + 1, mid + 1, right);
    }

    int treeHeight(TreeNode* root) 
    {
        if(root==NULL) return 0;
	    else if(root->left == NULL && root->right==NULL)
        return 1;
	    return max(treeHeight(root->left)+1,treeHeight(root->right)+1) ;
    }
};