在 C++ 中将二叉树展平为链表
c++server side programmingprogramming
假设我们有一棵二叉树;我们必须将其展平为链表。因此,如果树像 −
输出树将是 −
为了解决这个问题,我们将遵循以下步骤 −
ser prev := null
定义一个递归函数solve(),它将以root作为输入。
if root is null, then return
solve(right of root)
solve(left of root)
right of root := prev, left of root := null
prev := root
让我们看看下面的实现以便更好地理解 −
示例
#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,