题解 | #正则表达式匹配#

public class Solution {
    TreeNode head;
    public TreeNode Convert(TreeNode pRootOfTree) {
        cvert(pRootOfTree, false);
        return head;
    }
    // isLeft:root是否是父节点的左子树。左子树返回子树链表的tail，右子树返回子树链表的head
    TreeNode cvert(TreeNode root, boolean isLeft){
        if (root == null) return null;
        TreeNode left = cvert(root.left, true);
        // 设置head节点
        if (head == null) head = root;
        root.left = left;
        if (left != null)    left.right = root;
        TreeNode right = cvert(root.right, false);
        root.right = right;
        if (right != null) right.left = root;
        // 对tail或head为null的情况，用root替代
        if (isLeft && right == null) right = root;
        if (!isLeft && left == null) left = root;
        return isLeft ? right : left;
    }
}