蚌埠网站制作哪家靠谱_山西最新疫情更新_网络平台销售_网站优化包括

AC截图

题目

思路

可以先先序遍历把所有的结点存入数组中，然后再依次遍历数组重构二叉树。

代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void preOrder(TreeNode* root,vector<TreeNode*>& vec){if(root==NULL) return;vec.push_back(root);preOrder(root->left,vec);preOrder(root->right,vec);}void flatten(TreeNode* root) {if(root==NULL){return ;}vector<TreeNode*> vec;preOrder(root,vec);root = vec[0];root->left = NULL;root->right = NULL;if(vec.size()==1){return ;}int i;for(i=1;i<vec.size();i++){vec[i-1]->left = NULL;vec[i-1]->right = vec[i];}vec[i-1]->left = NULL;vec[i-1]->right = NULL;}
};

进阶思路

对于一棵二叉树，如果有左子树，则需要进行处理，如果没有，则无需处理

如果有左子树：

        找到该左子树最右的结点，下一个结点就应该是根结点的右子树。将该根结点的右子树拼接到左子树最右的结点的下一个结点，然后将整个左子树移为右子树。继续遍历。

进阶代码

class Solution {
public:void flatten(TreeNode* root) {TreeNode *curr = root;while (curr != nullptr) {if (curr->left != nullptr) { // 如果当前节点有左子树auto next = curr->left; // 下一个要处理的节点是当前节点的左子节点auto predecessor = next;// 找到左子树中的最右节点，即前驱节点while (predecessor->right != nullptr) {predecessor = predecessor->right;}// 将当前节点的右子树挂到前驱节点的右子树上predecessor->right = curr->right;// 断开当前节点与左子树的连接，并将其左子树变为右子树curr->left = nullptr;curr->right = next;}// 移动到下一个节点（即当前节点的新右子节点）curr = curr->right;}}
};