对任意给定的二叉树完成下列操作： （1）根据输入的序列，建立二叉链表存储结构； （2）输出该二叉树的先序、中序、后序遍历结果（递归算法）； （3）先序遍历二叉树（非递归算法）； （4）借助队列实现二叉树的层次遍历； （5）求二叉树的高度； （6）求二叉树叶子结点个数； （7）将二叉链表视为树或森林的孩子兄弟链表，计算其叶子结点个数。(c++)

二叉树的定义：

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

(1) 建立二叉链表存储结构：

TreeNode* buildTree(vector<int>& nums, int start, int end) {
    if (start > end) {
        return nullptr;
    }
    int mid = (start + end) / 2;
    TreeNode* root = new TreeNode(nums[mid]);
    root->left = buildTree(nums, start, mid - 1);
    root->right = buildTree(nums, mid + 1, end);
    return root;
}

(2) 输出二叉树的先序、中序、后序遍历结果（递归算法）：

void preOrder(TreeNode* root) {
    if (!root) {
        return;
    }
    cout << root->val << " ";
    preOrder(root->left);
    preOrder(root->right);
}

void inOrder(TreeNode* root) {
    if (!root) {
        return;
    }
    inOrder(root->left);
    cout << root->val << " ";
    inOrder(root->right);
}

void postOrder(TreeNode* root) {
    if (!root) {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    cout << root->val << " ";
}

(3) 先序遍历二叉树（非递归算法）：

void preOrderNonRecursive(TreeNode* root) {
    if (!root) {
        return;
    }
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* cur = s.top();
        s.pop();
        cout << cur->val << " ";
        if (cur->right) {
            s.push(cur->right);
        }
        if (cur->left) {
            s.push(cur->left);
        }
    }
}

(4) 借助队列实现二叉树的层次遍历：

void levelOrder(TreeNode* root) {
    if (!root) {
        return;
    }
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode* cur = q.front();
            q.pop();
            cout << cur->val << " ";
            if (cur->left) {
                q.push(cur->left);
            }
            if (cur->right) {
                q.push(cur->right);
            }
        }
    }
}

(5) 求二叉树的高度：

int getHeight(TreeNode* root) {
    if (!root) {
        return 0;
    }
    return max(getHeight(root->left), getHeight(root->right)) + 1;
}

(6) 求二叉树叶子结点个数：

int getLeafCount(TreeNode* root) {
    if (!root) {
        return 0;
    }
    if (!root->left && !root->right) {
        return 1;
    }
    return getLeafCount(root->left) + getLeafCount(root->right);
}

(7) 将二叉链表视为树或森林的孩子兄弟链表，计算其叶子结点个数：

int getLeafCount2(TreeNode* root) {
    if (!root) {
        return 0;
    }
    if (!root->left && !root->right) {
        return 1;
    }
    return getLeafCount2(root->left) + getLeafCount2(root->right);
}

int getLeafCount3(TreeNode* root) {
    if (!root) {
        return 0;
    }
    int leftCount = getLeafCount3(root->left);
    int rightCount = getLeafCount3(root->right);
    if (!root->left) {
        return rightCount;
    }
    if (!root->right) {
        return leftCount;
    }
    return leftCount + rightCount;
}