이진 트리가 있다고 가정합니다. 이것을 단일 연결 목록으로 변환해야 합니다.
따라서 입력이 다음과 같으면
그러면 출력은
이 문제를 해결하기 위해 다음 단계를 따릅니다.
-
이전 서버 :=null
-
입력으로 루트를 취하는 재귀 함수 solve()를 정의하십시오.
-
루트가 null이면 반환
-
해결(루트 오른쪽)
-
해결(루트 왼쪽)
-
루트의 오른쪽 :=이전, 루트의 왼쪽 :=null
-
이전 :=루트
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
예시
#include <bits/stdc++.h> using namespace std; class TreeNode{ public: int val; TreeNode *left, *right; TreeNode(int data){ val = data; left = NULL; right = NULL; } }; void insert(TreeNode **root, int val){ queue<TreeNode*> q; q.push(*root); while(q.size()){ TreeNode *temp = q.front(); q.pop(); if(!temp->left){ if(val != NULL) temp->left = new TreeNode(val); else temp->left = new TreeNode(0); return; }else{ q.push(temp->left); } if(!temp->right){ if(val != NULL) temp->right = new TreeNode(val); else temp->right = new TreeNode(0); return; }else{ q.push(temp->right); } } } TreeNode *make_tree(vector<int> v){ TreeNode *root = new TreeNode(v[0]); for(int i = 1; i<v.size(); i++){ insert(&root, v[i]); } return root; } class Solution { public: TreeNode* prev = NULL; void flatten(TreeNode* root) { if(!root) return; flatten(root->right); flatten(root->left); root->right = prev; root->left = NULL; prev = root; } }; main(){ vector<int> v = {1,2,5,3,4}; TreeNode *root = make_tree(v); Solution ob; (ob.flatten(root)); TreeNode *ptr = root; while(ptr != NULL && ptr->val != 0){ cout << ptr->val << ", "; ptr = ptr->right; } }
입력
{1,2,5,3,4}
출력
1, 2, 3, 4, 5,