Leetcode#95 Unique Binary Search Trees II
4330 단어 Binary search
Unique Binary Search Trees(이 문장 참조)의 업그레이드 버전
문제를 풀 때 나는 이것이 두 갈래 나무마다 독립적으로 하나를 만드는 것이 얼마나 번거로운지 생각했다.'공공부분'을 함께 사용할 수 있는지 시험해 보았는데, 과연 괜찮았구나, 하하.
trees[i][j]는 디지털 i부터 j까지 구성할 수 있는 모든 두 갈래 나무의 뿌리 노드를 나타낸다
코드:
1 vector<TreeNode *> generateTrees(int n) {
2 if (n < 1)
3 return vector<TreeNode *>(1, NULL);
4
5 vector<vector<vector<TreeNode *> > > trees(n + 1, vector<vector<TreeNode *> >(n + 1, vector<TreeNode *>()));
6
7 for (int len = 1; len <= n; len++) {
8 for (int i = 1, j = i + len - 1; j <= n; i++, j++) {
9 for (int k = i; k <= j; k++) {
10 vector<TreeNode *> lefts = k == i ? vector<TreeNode *>(1, NULL) : trees[i][k - 1];
11 vector<TreeNode *> rights = k == j ? vector<TreeNode *>(1, NULL) : trees[k + 1][j];
12 for (auto l : lefts) {
13 for (auto r : rights) {
14 TreeNode *node = new TreeNode(k);
15 node->left = l;
16 node->right = r;
17 trees[i][j].push_back(node);
18 }
19 }
20 }
21 }
22 }
23
24 return trees[1][n];
25 }이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[leetcode]_Validate Binary Search Tree제목: 두 갈래 나무 한 그루가 합법적인지 판단한다.두 갈래 트리가 왼쪽 트리의 모든 값생각: 1. 현재 루트 노드에서 판단하여 루트 노드의 왼쪽 트리 최대값 maxLeft, 오른쪽 트리 최소값 minRight를 구...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
