606. Construct String from Binary Tree 두 갈래 트리의 문자열 설명

1795 단어
You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way. The null node needs to be represented by empty parenthesis pair "()". And you need to omit all the empty parenthesis pairs that don't affect the one-to-one mapping relationship between the string and the original binary tree. 주어진 두 갈래 나무에 따라 만들어진 문자열을 되돌려주고 구축 원칙은 선순 서열 순서에 따라 하위 노드가 있는 것은 괄호로 묶고 잎 노드의 아이는 괄호가 생략된다.특히 왼쪽 아이가 존재하지 않고 아이가 존재한다면 왼쪽 아이의 괄호는 생략할 수 없다.
Example 1: Input: Binary tree: [1,2,3,4] 
       1
     /   \
    2     3
   /    
  4

Output: "1(2(4))(3)"Explanation: Originallay it needs to be "1(2(4)())(3()())", but you need to omit all the unnecessary empty parenthesis pairs. And it will be "1(2(4))(3)".
Example 2: Input: Binary tree: [1,2,3,null,4] 
       1
     /   \
    2     3
     \ 
      4

Output: "1(2()(4))(3)"Explanation: Almost the same as the first example, except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.
사고방식은 차례로 호출하면 된다.
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    string tree2str(TreeNode* t) {
        if(t==nullptr) return "";
        string res;
        res+=to_string(t->val);
        if(t->left) res+="("+tree2str(t->left)+")";
        else if( t->right) res+="()";
        if(t->right) res+="("+tree2str(t->right)+")";
        return res;
    }
};
선순과 중순으로 두 갈래 나무를 세우다
UVa 12166(문자 트리의 dfs)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage