力扣-面试题17.12题 BiNode（C++）- dfs

题目链接：https://leetcode-cn.com/problems/binode-lcci/
题目如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* convertBiNode(TreeNode* root) {
        //二叉搜索树的中序遍历是有序的

        dfs(root);

        return dummy->right;
    }
    void dfs(TreeNode* root){
        if(!root) return;
        
        TreeNode* left=root->left;
        TreeNode* right=root->right;

        dfs(left);

        tail->right=root;
        tail=root;
        root->left=nullptr;

        dfs(right);
    }
private:
    TreeNode* dummy=new TreeNode(-1);
    TreeNode* tail=dummy;//尾插节点
};