将一棵二叉树按照前序遍历拆解成为一个假链表。所谓的假链表是说，用二叉树的 right 指针，来表示链表中的 next 指针。

注意事项

不要忘记将左儿子标记为 null，否则你可能会得到空间溢出或是时间溢出。

样例

挑战

不使用额外的空间耗费。

标签

二叉树 深度优先搜索

方法一

使用栈保存暂时无法插入到链表的节点

code

/** * Definition of TreeNode: * class TreeNode { * public: *     int val; *     TreeNode *left, *right; *     TreeNode(int val) { *         this->val = val; *         this->left = this->right = NULL; *     } * } */class Solution {public:    /*     * @param root: a TreeNode, the root of the binary tree     * @return:      */    void flatten(TreeNode * root) {        // write your code here        if (root == NULL) {            return ;        }        stack
    
     stack;        TreeNode * node = root;        bool isContinue = true;        while (isContinue) {            if (node->left != NULL && node->right != NULL) {                stack.push(node->right);                node->right = node->left;                node->left = NULL;            }            else if (node->left != NULL && node->right == NULL) {                node->right = node->left;                node->left = NULL;            }            else if (node->left == NULL && node->right == NULL) {                if (!stack.empty()) {                    node->right = stack.top();                    stack.pop();                }                else {                    isContinue = false;                }            }            node = node->right;        }    }};
    

方法二

使用递归

code

/** * Definition of TreeNode: * class TreeNode { * public: *     int val; *     TreeNode *left, *right; *     TreeNode(int val) { *         this->val = val; *         this->left = this->right = NULL; *     } * } */class Solution {public:    /*     * @param root: a TreeNode, the root of the binary tree     * @return:      */    void flatten(TreeNode * root) {        // write your code here        if (root == NULL) {            return;        }        switchToLink(root);    }    TreeNode* switchToLink(TreeNode* root) {        if (root == NULL) {            return NULL;        }        TreeNode* left = switchToLink(root->left);        TreeNode* right = switchToLink(root->right);        if (left != NULL) {            left->right = root->right;            root->right = root->left;        }        root->left = NULL;        if (right != NULL) {            return right;        }        else if (left != NULL) {            return left;        }        else {            return root;        }    }};