【力扣】114.二叉树展开为链表

在做这个题目之前，如果可以的话，请先将144.前序遍历的题目做一下，这样你将会对前序、中序、后序遍历有一个比较清晰的了解。特别是这三者与递归相结合，嗯，真的很有意思。

?关于这道题，我会给出两种解法。其中法二是对法一的优化。

法一：递归+数组

题解：

通过前序遍历将每个结点存入数组中，类型为TreeNode，然后对数组进行处理使其符合题目要求。代码如下：

/**
 * 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 preoder(TreeNode* root,vector<TreeNode*>s){
        if(root==nullptr) return;
        s.push_back(root);
        preoder(root->left,s);
        preoder(root->right,s);
    }
    //对经过遍历之后的数组进行处理
    void flatten(TreeNode* root) {
        vector<TreeNode*>s;
        preoder(root,s);
        for(int i=1;i<s.size();i++){
            TreeNode* prev=s.at(i-1),*curr=s.at(i);
            prev->left=nullptr;
            prev->right=curr;
        }
    }
};

法二：迭代+栈

题解：

用这个方法的目的就解决了不用将所有结点全放进数组里面之后再进行处理，而是边走边变。那在这里用栈，需要注意的是顺序，因为我们还是前序遍历，先左后右，而栈的特性是先入后出。所以我们在迭代的时候需要先让右子树先进。后面的话那就很简单了。看代码：

/**
 * 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 flatten(TreeNode* root) {
        if(root==nullptr) return ;
        auto stk=stack<TreeNode*>();
        stk.push(root);  //先将根元素压入栈
        TreeNode* prev=nullptr;
        while(!stk.empty()){
            TreeNode *curr=stk.top();
            stk.pop();
            if(prev!=nullptr){
                prev->left=nullptr;
                prev->right=curr;
            }
            TreeNode* left=curr->left,*right=curr->right;
            //将当前节点的右左树压入栈中即可
            if(right!=nullptr){
                stk.push(right);
            }
            if(left!=nullptr){
                stk.push(left);
            }
            prev=curr;
        }
    }
};

嗨，同学~

请记得在奔跑的同时也不要错过路上的风景哦，加油！