두 갈래 나무 유형 OJ 문제편 1
95579 단어 참혹한 문제 풀이 기록
두 갈래 나무 유형 문제
1. 왼쪽 잎의 합
두 갈래 나무에 주어진 모든 왼쪽 잎의 합을 계산하다
3
/ \
9 20
/ \
15 7
이 두 갈래 나무 중에는 두 개의 왼쪽 잎이 있는데, 각각 9와 15이기 때문에 24로 돌아간다
방법1: 귀속
def sumOfLeftLeaves(self, root: TreeNode) -> int:
if not root:
return 0
#
if root.left and not root.left.left and not root.left.right:
return root.left.val + self.sumOfLeftLeaves(root.right)
#
return self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)
방법2: 비귀속
하나의 대기열로 두 갈래 나무를 층차적으로 훑어보고 왼쪽 나무의 잎 노드라면 반환 변수에 추가합니다
int sumOfLeftLeaves(TreeNode* root) {
queue<TreeNode*>q;
if(root == nullptr){
return 0;
}
q.push(root);
int ans = 0;
while(!q.empty()){
TreeNode* temp = q.front();
q.pop();
if(temp->left && temp->left->left == nullptr
&& temp->left->right == nullptr){
ans+=temp->left->val;
}
if(temp->left){
q.push(temp->left);
}
if(temp->right){
q.push(temp->right);
}
}
return ans;
}
2, 두 갈래 나무의 모든 경로
두 갈래 나무를 정해서 뿌리 노드에서 잎 노드까지의 모든 경로를 되돌려줍니다
설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다
, :
1
/ \
2 3
\
5
: ["1->2->5", "1->3"]
방법1: 귀속
먼저 왼쪽 나무를 수색한 다음에 오른쪽 나무를 수색하여 방문한 노드가 멈추는 조건을 기록하는 것은 잎 노드, 즉 이 노드에 아이 노드가 없다는 것이다. 이때 삽입한 후에 그것을 사용한다
-> 분할해 def binaryTreePaths(self, root: TreeNode) -> List[str]:
res = []
if not root:
return res
def dfs(root,path):
if not root.left and not root.right:
res.append('->'.join(path+[str(root.val)]))
if root.left:
dfs(root.left,path+[str(root.val)])
if root.right:
dfs(root.right,path+[str(root.val)])
dfs(root,[])
return res
C++ 버전: 기본 일관성
void dfs(TreeNode* root,string str,vector<string>&res){
if(root->left == NULL && root->right==NULL){
str += to_string(root->val);
res.push_back(str);
return;
}
str +=to_string(root->val) + "->";
if (root->left){
dfs(root->left,str,res);
}
if (root->right){
dfs(root->right,str,res);
}
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string>res;
if(root == NULL){
return res;
}
string str = "";
dfs(root,str,res);
return res;
}
방법2: 비귀속, 창고 이용
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> ans;
if(root==NULL) {
return ans;
}
TreeNode* p=root;
stack<pair<TreeNode*,string>> s;
string str;
while(!s.empty() || p){
while(p){
if(p==root){
str=str+to_string(p->val);
}else{
str=str+"->"+to_string(p->val);
}
s.push(pair<TreeNode*,string>(p,str));
p=p->left;
}
p=s.top().first;
str=s.top().second;
s.pop();
if(p->right==NULL&&p->left==NULL)
ans.push_back(str);
p=p->right;
}
return ans;
}
비귀속, 대기열 활용
vector<string> binaryTreePaths(TreeNode* root) {
vector<string>res;
if(root == nullptr){
return res;
}
queue<pair<TreeNode*,string>>q;
q.push(pair<TreeNode*,string>\
(root,to_string(root->val)));
while(!q.empty()){
TreeNode* node = q.front().first;
string path = q.front().second;
q.pop();
if(node->left == nullptr &&
node->right == nullptr){
res.push_back(path);
}
if(node->left){
q.push(pair<TreeNode*,string>\
(node->left,path + "->"+to_string\
(node->left->val)));
}
if(node->right){
q.push(pair<TreeNode*,string>\
(node->right,path + "->"+to_string\
(node->right->val)));
}
}
return res;
}
3. 두 갈래 나무를 뒤집는다
두 갈래 나무 한 그루를 뒤집다
방법1: 귀속
def invertTree(self, root: TreeNode) -> TreeNode:
if root:
root.left,root.right = self.invertTree(root.right),self.invertTree(root.left)
return root
C++ 버전
TreeNode* invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode* temp = root->left;
root->left = invertTree(root->right);
root->right = invertTree(temp);
return root;
}
방법2: 비귀속, 하나의 대열을 이용하여 교체한다
TreeNode* invertTree(TreeNode* root) {
if(root==nullptr){
return nullptr;
}
queue<TreeNode*>que;
que.push(root);
while(!que.empty()){
TreeNode* cur = que.front();
que.pop();
TreeNode* temp = cur->left;
cur->left = cur->right;
cur->right = temp;
if(cur->left){
que.push(cur->left);
}
if(cur->right){
que.push(cur->right);
}
}
return root;
}
4, 두 갈래 나무의 오른쪽 보기
두 갈래 나무를 정해서 오른쪽에 서 있는 것을 상상하고 꼭대기에서 끝까지 순서대로 오른쪽에서 볼 수 있는 노드 값을 되돌려준다
예시 입력: [1,2,3,null, 5,null, 4] 출력: [1,3,4]
1
/ \
2 3
\ \
5 4
사고방식: 사실은 한 단계를 두루 훑어보고 각 층의 마지막 노드를 되돌아오는 목록에 추가하는 것이다.
def rightSideView(self, root: TreeNode) -> List[int]:
if not root:
return []
temp = [root]
res = []
while temp:
res.append(temp[-1].val)
temp = [kid for node in temp for kid in [node.left,node.right]if kid]
return res
C++ 버전
vector<int> rightSideView(TreeNode* root) {
vector<int>res;
if(!root){
return res;
}
queue<TreeNode*>q;
q.push(root);
while (!q.empty()){
int size = q.size();
res.push_back(q.front()->val);
while (size--){
TreeNode* temp = q.front();
q.pop();
if (temp->right){
q.push(temp->right);
}
if (temp->left){
q.push(temp->left);
}
}
}
return res;
}
5. 두 갈래 나무 재건
전차수열과 중차수열에 따라 두 갈래 트리 구축
전차 역행 preorder = [3,9,20,15,7] 중차 역행 inorder = [9,3,15,20,7]
출력
3
/ \
9 20
/ \
15 7
사고방식: 앞의 첫 번째 노드는 루트 루트 노드입니다. 이 루트 노드에 따라 중간 노드에서 왼쪽 트리와 오른쪽 트리로 나누어 두 갈래 트리를 구축합니다.
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int end = preorder.size()-1;
return build(preorder,inorder,0,0,end);
}
TreeNode* build(vector<int>& preorder, vector<int>& inorder,\
int root,int start,int end)
{
if(start>end){
return nullptr;
}
TreeNode* tree = new TreeNode(preorder[root]);
int i = start;
while(i<end && preorder[root] != inorder[i]){
++i;
}
tree->left = build(preorder,inorder,root+1,start,i-1);
tree->right = build(preorder,inorder,root+1+i-start,i+1,end);
return tree;
}
python 쓰기
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder:
return None
local = inorder.index(preorder[0])
root = TreeNode(preorder[0])
root.left = self.buildTree(preorder[1:local+1],inorder[:local])
root.right = self.buildTree(preorder[local+1:],inorder[local+1:])
return root
중간 순서 목록에 unordered_ 설정 가능map 용기, 편리bianli
unordered_map<int, int> mp;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for (int i = 0; i < inorder.size(); i++) {
mp[inorder[i]] = i;
}
return dfs(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
}
TreeNode* dfs(const vector<int>& preorder, int pl, int pr, const vector<int>& inorder, int il, int ir) {
if (pl > pr) return NULL;
TreeNode *root = new TreeNode(preorder[pl]);
int idx = mp[root->val];
int cntL = idx - il;
root->left = dfs(preorder, pl + 1, pl + cntL, inorder, il, idx-1);
root->right = dfs(preorder, pl + cntL + 1, pr, inorder, idx+1, ir);
return root;
}
만약 위의 코드가 이해하기 어렵다면, 이것은 비교적 간단해야 한다
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(vin.size()==0){
return 0;
}
//
vector<int>pre_left,pre_right,vin_left,vin_right;
// ，
TreeNode* root = new TreeNode(pre[0]);
int temp = 0;
for(int i = 0;i < vin.size();++i){
if(vin[i] == pre[0]){
temp = i;
break;
}
}
for(int i = 0;i < temp;++i){
pre_left.push_back(pre[i+1]);
vin_left.push_back(vin[i]);
}
for(int i = temp+1;i < vin.size();++i){
pre_right.push_back(pre[i]);
vin_right.push_back(vin[i]);
}
root->left = reConstructBinaryTree(pre_left,vin_left);
root->right = reConstructBinaryTree(pre_right,vin_right);
return root;
}
6. 지그재그 순서로 두 갈래 나무를 인쇄한다
함수는 지그재그로 두 갈래 트리를 인쇄합니다. 즉, 첫 번째 줄은 왼쪽에서 오른쪽으로, 두 번째 줄은 오른쪽에서 왼쪽으로, 세 번째 줄은 왼쪽에서 오른쪽으로, 다른 줄은 이와 같이 인쇄합니다.
예:
1
/ \
2 3
/ \ / \
4 5 6 7
먼저 1을 인쇄한 다음에 3, 2를 인쇄한 다음에 4, 5, 6, 7을 인쇄하는 규칙은 홀수 줄은 왼쪽에서 오른쪽으로, 짝수 줄은 오른쪽에서 왼쪽으로 하는 것이다
두 개의 창고를 이용하여 교환하여 저장하는데, 코드가 보기에는 매우 많지만, 그래도 비교적 이해하기 쉽다
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int>>res;
if(pRoot == nullptr){
return res;
}
// ，
stack<TreeNode*>s1;
stack<TreeNode*>s2;
vector<int>temp;//
temp.push_back(pRoot->val);
res.push_back(temp);
s1.push(pRoot);
temp.clear();
while(!s1.empty() || !s2.empty()){
while(!s1.empty()){
// s1 ，
TreeNode* node = s1.top();
s1.pop();
if(node->right){
s2.push(node->right);
temp.push_back(node->right->val);
}
if(node->left){
s2.push(node->left);
temp.push_back(node->left->val);
}
}
// ，
if(!temp.empty()){
res.push_back(temp);
temp.clear();
}
while(!s2.empty()){
// s2 ，
TreeNode* cur = s2.top();
s2.pop();
if(cur->left){
s1.push(cur->left);
temp.push_back(cur->left->val);
}
if(cur->right){
s1.push(cur->right);
temp.push_back(cur->right->val);
}
}
// ，
if(!temp.empty()){
res.push_back(temp);
temp.clear();
}
}
return res;
}
방법 2:
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>>res;
if(root == nullptr){
return res;
}
queue<TreeNode*>q;
q.push(root);
bool isLeft = false;
while(!q.empty()){
int size = q.size();
vector<int>temp;
for(int i = 0;i<size;++i){
TreeNode* node = q.front();
q.pop();
temp.push_back(node->val);
if(node->left){
q.push(node->left);
}
if(node->right){
q.push(node->right);
}
}
isLeft = !isLeft;
if(!isLeft){
res.push_back(vector<int>(temp.rbegin(),temp.rend()));
}else{
res.push_back(temp);
}
}
return res;
}
};
7. 서열화 두 갈래 나무
두 함수를 실현하십시오. 각각 서열화와 반서열화 두 갈래 나무에 쓰십시오
두 갈래 나무의 서열화란 한 그루의 두 갈래 나무를 어떤 역행 방식의 결과에 따라 어떤 형식으로 문자열로 저장하여 메모리에 세워진 두 갈래 나무를 오래 보존할 수 있도록 하는 것을 말한다.서열화는 선순, 중순, 후순, 층순의 두 갈래 트리 역행 방식을 바탕으로 수정할 수 있습니다. 서열화의 결과는 문자열입니다. 서열화할 때 어떤 기호를 통해 빈 노드(#)를 나타냅니다!결점 값의 끝을 표시합니다 (value!)
두 갈래 나무의 반서열화란 어떤 반복 순서에 따라 얻어진 서열화 문자열 결과str, 두 갈래 나무를 재구성하는 것을 가리킨다
class Solution {
public:
char* Serialize(TreeNode *root) {
buf.clear();
SerializePre(root);
int size = buf.size();
int* res = new int[size];
for(int i = 0;i < size;++i){
res[i] = buf[i];
}
return (char*)res;
}
TreeNode* Deserialize(char *str) {
int* p = (int*)str;
return DeserializePre(p);
}
private:
// ,
void SerializePre(TreeNode *root){
if(root == nullptr){
buf.push_back(0xFFFFFFFF);
}else{
buf.push_back(root->val);
SerializePre(root->left);
SerializePre(root->right);
}
}
//
TreeNode* DeserializePre(int* &p){
if(*p == 0xFFFFFFFF){
p++;
return nullptr;
}
TreeNode* res = new TreeNode(*p);
p++;
res->left = DeserializePre(p);
res->right = DeserializePre(p);
return res;
}
private:
vector<int>buf;
};
8, 두 갈래 트리 검색 트리의 k번째 노드
TreeNode* res = nullptr;
int count = 0;
TreeNode* KthNode(TreeNode* pRoot, int k){
if(pRoot == nullptr || k < 1){
return nullptr;
}
count = k;
KthNodeIn(pRoot);
return res;
}
void KthNodeIn(TreeNode* pRoot){
if(pRoot == nullptr){
return;
}
KthNodeIn(pRoot->left);
if(--count ==0){
res = pRoot;
}
KthNodeIn(pRoot->right);
}
좋은 웹페이지 즐겨찾기
