1.计算二叉树所有节点数和叶子节点数

#include <iostream>
#include<stack>
using namespace std;
int num=0;
int num2=0;
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int pre_order(TreeNode*root)
{
    if(!root)return 0;
    return 1+pre_order(root->left)+pre_order(root->right);
}
int  post_order(TreeNode*root)
{
    if(!root)return 0;
    if(!root->left&&!root->right)return 1;
    return post_order(root->left)+post_order(root->right);
}
int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    pre_order(root);
    cout << "节点个数为" << pre_order(root)<< endl;
    cout <<"叶子节点个数为"<<post_order(root)<<endl;

}

2.把二叉树叶子节点串成单链表

#include <iostream>
#include <queue>
using namespace std;

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

struct Node {
    TreeNode* val;
    Node* next;
    Node(TreeNode* x) : val(x), next(nullptr) {}
};

Node* to_list(TreeNode* root) {
    if (!root) return nullptr;

    queue<TreeNode*> q;
    queue<TreeNode*> leaf; // 用于存储叶节点

    q.push(root);
    while (!q.empty()) {
        TreeNode* x = q.front();
        q.pop();

        if (!x->left && !x->right) { // 如果是叶子节点，加入到leaf队列里
            leaf.push(x);
        }
        if (x->left) q.push(x->left);
        if (x->right) q.push(x->right);
    }

    // head指向第一个叶子节点，tail指向最后一个叶子节点
    Node* head = nullptr;
    Node* tail = nullptr;

    while (!leaf.empty()) {
        Node* node = new Node(leaf.front());
        leaf.pop();

        if (tail == nullptr) {
            head = node;
            tail = node;
        } else {
            tail->next = node;
            tail = node;
        }
    }
    return head;
}

void print_list(Node* head) {
    while (head) {
        cout << head->val->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    Node* leaf_list = to_list(root);
    print_list(leaf_list);
    return 0;
}

3.增加双亲指针，输出所有节点到根节点的路径

#include <iostream>
#include<stack>
using namespace std;

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

// 输出从当前节点到根节点（不包括根节点）的路径
void print_single_path(TreeNode* cur) {
    if (!cur) return;  // 如果节点为空，直接返回

    // 使用栈来保存路径
    stack<int> path;
    TreeNode* temp = cur;

    // 从当前节点沿着 parent 指针回溯到根节点
    while (temp) {
        path.push(temp->val);
        temp = temp->parent;
    }

    // 从栈中弹出节点值并打印（这样是从当前节点到根节点的路径）
    while (!path.empty()) {
        cout << path.top() << " ";
        path.pop();
    }
    cout << endl;  // 换行表示一条路径结束
}

// 遍历树并输出每个节点到根节点（不包括根节点）的路径
void print_all_paths(TreeNode* root) {
    if (!root) return;

    // 递归处理左子树
    if (root->left) {
        print_single_path(root->left);
        print_all_paths(root->left);
    }

    // 递归处理右子树
    if (root->right) {
        print_single_path(root->right);
        print_all_paths(root->right);
    }
}

int main() {
    // 构造二叉树并设置父节点指针
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->parent = root;
    root->right->parent = root;
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->left->left->parent = root->left;
    root->left->right->parent = root->left;

    // 输出所有节点到根节点的路径（不包括根节点）
    print_all_paths(root);

    return 0;
}

4.满二叉树先序遍历转为后序遍历

#include <iostream>
using namespace std;

const int N = 100;
int pre[N];
int post[N];
int cnt = 0;

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

// 先序遍历并保存到数组 pre 中
void pre_order(TreeNode* root) {
    if (!root) return;
    pre[cnt++] = root->val;
    pre_order(root->left);
    pre_order(root->right);
}

// 将满二叉树的先序遍历转换为后序遍历
void pre_to_post(int pre[], int a, int b, int post[], int x, int y) {
    if (a > b) return;

    // 根节点
    post[y] = pre[a];

    int half = (b - a) / 2; // 左右子树的元素数量相同

    // 递归处理左子树
    pre_to_post(pre, a + 1, a + half, post, x, x + half - 1);

    // 递归处理右子树
    pre_to_post(pre, a + half + 1, b, post, x + half, y - 1);
}

int main() {
    // 创建一个满二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    // 先序遍历
    pre_order(root);

    // 输出先序遍历序列
    cout << "Pre-order: ";
    for (int i = 0; i < cnt; ++i) {
        cout << pre[i] << " ";
    }
    cout << endl;

    // 将先序转换为后序
    pre_to_post(pre, 0, cnt - 1, post, 0, cnt - 1);

    // 输出后序遍历序列
    cout << "Post-order: ";
    for (int i = 0; i < cnt; ++i) {
        cout << post[i] << " ";
    }
    cout << endl;

    return 0;
}

5.求值为x节点的层次号

#include <iostream>
#include <queue>
using namespace std;
const int N = 100;
int res=0;
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode* parent;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr), parent(nullptr) {}
};

//返回值为x节点的层次号
int depth(TreeNode*root,int x)
{
    queue<TreeNode*>q;
    q.push(root);
    int level=0;
    while(!q.empty())
    {
        int size=q.size();
        for(int i=0;i<size;i++)
        {
        TreeNode*cur=q.front();
        q.pop();
        if(cur->val==x)return level;
        if(cur->left)q.push(cur->left);
        if(cur->right)q.push(cur->right);
        }
        level++;
    }
    return -1;
}

int main() {

      TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    cout<<depth(root,5)<<endl;
    return 0;
}

6.二叉树最大宽度

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

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

// 计算最大宽度
int max_length(TreeNode* root) {
    if (!root) return 0;
    queue<TreeNode*> q;
    q.push(root);
    int max_width = 0;
    while (!q.empty()) {
        int size = q.size();
        if (size > max_width) max_width = size;
        for (int i = 0; i < size; i++) {
            TreeNode* cur = q.front();
            q.pop();
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
    }
    return max_width;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    cout << " 二叉树最大宽度: " << max_length(root) << endl;

    return 0;
}

7.统计度为1的节点数目

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

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

// 计算度为1的节点数
int node(TreeNode* root) {
    if (!root) return 0;
    queue<TreeNode*> q;
    q.push(root);
    int res = 0;
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode* cur = q.front();
            if(cur->left&&!cur->right||cur->right&&!cur->left)res++;
            q.pop();
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
    }
    return res;
}
int pre_order(TreeNode*root)
{
    if(!root)return 0;
    if(root->left&&!root->right)return 1;
    if(root->right&&!root->left)return 1;
    return pre_order(root->left)+pre_order(root->right);
}
int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);


    cout << " 度为1的节点个数: " << pre_order(root) << endl;

    return 0;
}

8.求任意二叉树中第一条最长的路径长度，并输出此路径上各节点的值

#include <iostream>
#include <vector>
using namespace std;

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

// 计算最长路径的长度并保存路径
int max_length(TreeNode* root, vector<int>& path) {
    if (!root) return 0;

    vector<int> leftPath, rightPath;
    int left = max_length(root->left, leftPath);//左
    int right = max_length(root->right, rightPath);//右
    //单层递归逻辑
    if (left > right) {
        path = leftPath;
    } else {
        path = rightPath;
    }
    path.push_back(root->val);//中
    return max(left, right) + 1;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);

    vector<int> path;
    int length = max_length(root, path);

    cout << "第一条最长路径长度: " << length << endl;
    cout << "路径上的节点值: ";
    for (int i = path.size() - 1; i >= 0; --i) {
        cout << path[i] << " ";
    }
    cout << endl;

    return 0;
}