给你二叉树的根结点 root ，请你将它展开为一个单链表： 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。 展开后的单链表应该与二叉树 先序遍历 顺序相同

将二叉树 root 展开为单链表，可以使用递归的方法：首先判断 root 是否为空，如果是，则返回空；如果不是，则先展开 root 的左子树，然后将 root 的左子结点置为空，把 root 的右子结点连接到展开后的左子树的末尾，再展开 root 的右子树，然后将 root 连接到展开后的右子树的末尾，最后返回展开后的单链表的头结点。

相关问题

将二叉树的叶结点按从左到右的顺序连成一个单链表

### 回答1：
将二叉树的叶节点按从左到右的顺序连接成一个单链表，可以采用深度优先搜索的方法，先遍历左子树，再遍历右子树，最后将叶节点连接成链表。

具体步骤如下：

1. 如果当前节点为空，则返回。

2. 如果当前节点是叶节点，则将其加入链表中。

3. 递归遍历左子树。

4. 递归遍历右子树。

5. 返回链表的头节点。

代码实现如下：

class Solution {
public:
    TreeNode* pre = NULL;
    TreeNode* head = NULL;

    TreeNode* convert(TreeNode* root) {
        if (root == NULL) return NULL;
        if (root->left == NULL && root->right == NULL) {
            if (pre == NULL) head = root;
            else pre->right = root;
            pre = root;
            return NULL;
        }
        root->left = convert(root->left);
        root->right = convert(root->right);
        return head;
    }
};

其中，pre表示当前链表的尾节点，head表示链表的头节点。在遍历到叶节点时，将其加入链表中，并更新pre指针。最后返回head指针即可。

### 回答2：
将二叉树的叶结点按从左到右的顺序连成一个单链表，需要按照以下步骤：

1. 判断二叉树根节点是否为空，若为空则直接返回空链表；

2. 判断根节点的左右子树是否为空，若左右子树都为空，则将根节点作为叶节点加入到链表中；

3. 若左子树为空，递归处理右子树；

4. 若右子树为空，递归处理左子树；

5. 若左右子树都不为空，则递归处理左右子树，将左子树的叶节点和右子树的叶节点分别按照顺序连接到一起，并将根节点从链表中删除，返回新的链表头节点。

代码实现如下：

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

ListNode* leafList(TreeNode* root) {
    if (!root) return NULL;
    if (!root->left && !root->right) return new ListNode(root->val);
    ListNode *leftList = leafList(root->left);
    ListNode *rightList = leafList(root->right);
    if (!leftList) return rightList;
    if (!rightList) return leftList;
    ListNode *cur = leftList;
    while (cur->next) cur = cur->next;
    cur->next = rightList;
    delete root;
    return leftList;
}

该函数传入二叉树的根节点，返回链表的头节点。时间复杂度为O(n)，空间复杂度为O(logn)。

### 回答3：
首先，需要了解什么是二叉树和单链表。二叉树是一种树形结构，其中每个节点最多有两个子节点，即左子树和右子树。而单链表是一种线性结构，每个节点都只有一个后继节点。

将二叉树的叶结点按照从左到右的顺序连成一个单链表，可以通过递归遍历二叉树实现。

首先，判断当前节点是否为叶结点，如果是，则将该节点加入到单链表中。如果不是叶结点，则递归遍历其左子树和右子树。

为了将左右子树的叶结点按照从左到右的顺序加入到单链表中，可以采用一个辅助函数，该函数的作用是将两个单链表合并成一个单链表。合并时，需要遍历第一个单链表，找到其最后一个节点，然后将第二个单链表接在其后面。

最后，递归返回时，返回合并后的单链表即可。

具体实现可以参考以下代码：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* mergeLists(ListNode* head1, ListNode* head2) {
    if (!head1 || !head2) {
        return head1 ? head1 : head2;
    }
    ListNode* cur = head1;
    while (cur->next) {
        cur = cur->next;
    }
    cur->next = head2;
    return head1;
}

ListNode* convert(TreeNode* root) {
    if (!root) {
        return NULL;
    }
    if (!root->left && !root->right) {
        return new ListNode(root->val);
    }
    ListNode* leftList = convert(root->left);
    ListNode* rightList = convert(root->right);
    return mergeLists(leftList, rightList);
}

以上代码中，convert函数用于将二叉树的叶结点转换成单链表，mergeLists函数用于合并两个单链表。使用时，只需要调用convert(root)即可。

给你一颗二叉树，请你求出该二叉树的结点总数。

好的，这是一道经典的二叉树问题。我可以给你一个递归的解法。

首先，如果二叉树为空，节点数为0。否则，可以把二叉树拆分成左子树和右子树两部分，分别求出它们的节点数，然后加上根节点，即可得到整棵树的节点数。具体的实现可以参考下面的代码：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def countNodes(root: TreeNode) -> int:
    if not root:
        return 0
    left_height = get_height(root.left)
    right_height = get_height(root.right)
    if left_height == right_height:
        # 左子树是一棵满二叉树，右子树是一棵普通二叉树
        return (1 << left_height) + countNodes(root.right)
    else:
        # 右子树是一棵满二叉树，左子树是一棵普通二叉树
        return (1 << right_height) + countNodes(root.left)

def get_height(root: TreeNode) -> int:
    height = 0
    while root:
        height += 1
        root = root.left
    return height

其中，`countNodes` 函数用于计算二叉树的节点数，`get_height` 函数用于计算一棵满二叉树的高度。这个算法的时间复杂度是 $O(\log^2 n)$，其中 $n$ 是二叉树的节点数。