노드 수에 따라 만 두 갈래 트리 구축

1547 단어 두 갈래 나무

894. All Possible Full Binary Tree


A full binary tree is a binary tree where each node has exactly 0 or 2 children.
Return a list of all possible full binary trees with N nodes.  Each element of the answer is the root node of one possible tree.
Each node of each tree in the answer must have node.val = 0 .
You may return the final list of trees in any order.
 
Example 1:
Input: 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
Explanation:

 
Note:
  • 1 <= N <= 20

  • 문제: 밑바닥에서 정상층으로 구축한다. 예를 들어 현재 구축 노드 수가 5인 만 두 갈래 나무가 필요하면 가능한 것은 왼쪽 나무 1개, 오른쪽 나무 3개로 나눌 수 있다.또는 왼쪽 나무 3개, 오른쪽 나무 1개;2-2의 구분은 합법적이지 않다.그러면 밑바닥이 이미 구축되었을 때 왼쪽, 오른쪽 나무의 조합만 일일이 열거하면 된다.
    class Solution {
    public:
        vector allPossibleFBT(int N) {
            vectorans;
            if(N==1){
                ans.push_back(new TreeNode(0));
                return ans;
            }
            if(N%2==0) return ans;  // 
            for(int i=1;ileft=l;
                        tmp->right=r;
                        ans.push_back(tmp);
                    }
                }
            }
            return ans;
        }
    };
    

    좋은 웹페이지 즐겨찾기