递归实现，思路简单清晰OA，O(1)额外空间，欢迎大家评判

因为左右对称，我们只分析一侧，以左侧为例
对任意节点，若

1. 其左子节点非空：
   则其左邻居为左子节点的最右子孙节点
   递归处理左子节点
   将左指针指向左邻居，左邻居的右指针指向该节点
2. 其左子节点为空：
   则其左邻居为其祖先节点（即对称的情况1）
   无需处理（交由情况1处理）
   （二叉树非空指针数 = 空指针数 - 2）

上代码
Tips: 为了防止破坏树结构，必须在递归完子树后再修改自身节点与左/右邻居

class Solution {
public:
    //找左邻居
    TreeNode* findLeftNeigh(TreeNode* now){
        now = now->left;
        while(now->right){
            now = now->right;
        }
        return now;
    }
    //找右邻居
    TreeNode* findRightNeigh(TreeNode* now){
        now = now->right;
        while(now->left){
            now = now->left;
        }
        return now;
    }
    //递归判断
    void DFS(TreeNode* now){
        if(now->left){
            TreeNode* leftNeigh = findLeftNeigh(now);
            DFS(now->left);
            //因为调整指针会破坏树结构，所以在处理完整个左子树后在调整本节点左指针
            now->left = leftNeigh;
            leftNeigh->right = now;
        }
        if(now->right){
            TreeNode* rightNeigh = findRightNeigh(now);
            DFS(now->right);
            //同上
            now->right = rightNeigh;
            rightNeigh->left = now;
        }
    }
    //入口函数
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(!pRootOfTree) return pRootOfTree;
        TreeNode* head = pRootOfTree;
        while(head->left){
            head = head->left;
        }
        DFS(pRootOfTree);
        return head;
    }
};