树大题相关代码

作者： 作者的头像   Yotu ,  2024-09-17 21:46:47 ,  所有人可见 ,  阅读 3

1


1

非递归求从下至上，从右至左的树的遍历

// 非递归求从下至上，从右至左的树的遍历
void invertLevelOrder(TreeNode* root){
    queue<TreeNode*> q;
    stack<TreeNode*> s;

    q.push(root);

    while(!q.empty()){
        auto t = q.front();
        q.pop();
        s.push(t);
        if(t->left) q.push(t->left);
        if(t->right) q.push(t->right);
    }

    while(!s.empty()){
        auto t = s.top();
        cout << t->val << ' ';
        s.pop();
    }
    cout << endl;
}

递归求树的高度

// 递归求树的高度
int heigh(TreeNode* root){
    if(!root) return 0;
    return max(heigh(root->left),heigh(root->right))+1;
}

非递归求树的高度


//非递归求树的高度
int heigh2(TreeNode* root){

    int h = 0;
    queue<TreeNode*> q;
    q.push(root);

    while(!q.empty()){

        // 记录队列中的元素，也就是当前层的元素个数
        int n = q.size();

        while(n--){
            auto t = q.front();
            q.pop();
            if(t->left) q.push(t->left);
            if(t->right) q.push(t->right);
        }
        h++;
    }
    return h;
}

求树的最大宽度


//求树的最大宽度
int width(TreeNode* root){

    //定义大根堆,用来存储每一层的宽度
    priority_queue<int> maxwidth;
    queue<TreeNode*> q;

    q.push(root);
    while(!q.empty()){

        int n = q.size();
        maxwidth.push(n);

        while(n--){
            auto t = q.front();
            q.pop();
            if(t->left) q.push(t->left);
            if(t->right) q.push(t->right);
        }
    }

    return maxwidth.top();
}

返回最近的公共祖先节点

//求最近公共祖先
// 返回根结点到p的路径
vector<TreeNode *> findPath(TreeNode *root, TreeNode *p)
{
    vector<TreeNode*> s;
    TreeNode *cur = root, *pre = NULL;
    while (cur || s.size())
    {
        while (cur)
        {
            s.push_back(cur);
            cur = cur->left;
        }

        cur = s.back();
        if (cur->right && cur->right != pre)
            cur = cur->right;
        else
        {
            s.pop_back();
            if (cur == p)
                return s;
            pre = cur;
            cur = NULL;
        }
    }
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
    vector<TreeNode *> path1 = findPath(root, p);
    vector<TreeNode *> path2 = findPath(root, q);

    if (path1.size() > path2.size()) swap(path1, path2);
    for (int i = 0; i < path1.size(); i ++)
        if (path1[i] != path2[i])
            return path1[i - 1];
    return path1.back();
}

判定是否是完全二叉树

//判定是否是完全二叉树

/*
1. 如果某节点有右子树，无左子树，则不是完全二叉树
2. 如果这个节点左子树存在，但其左兄弟的右子树不存在，则不是完全二叉树；



*/


bool isCompleteTree(TreeNode* root){

    queue<TreeNode*> q;
    q.push(root);
    bool leaf = false;

    while(!q.empty()){

        auto t = q.front();
        q.pop();

        //如果遇到根节点
        if(t == NULL){
            leaf = true;
            continue;  // 跳过这层循环，直接进入下一层循环
        }

        if(leaf && t) return false;
        else{
            q.push(t->left);
            q.push(t->right);
        }
    }
    return true; 
}

求双分支节点个数

//求双分支节点个数

int res = 0;

void dfs(TreeNode* root){
    if(!root) return;
    if(root->left && root->right) res++;
    if(root->left) dfs(root->left);
    if(root->right) dfs(root->right);
}

交换左右子树


//交换左右子树
/*
基于后序遍历, [注]前序，后序遍历都可以实现，但中序遍历不可实现
*/
void exchange(TreeNode* root){
    if(!root) return; 
    exchange(root->left);
    exchange(root->right);
    swap(root->left,root->right);
}
/*
基于前序遍历的交换左右子树
*/
// void exchange(TreeNode* root){
//     if(!root) return; 
//     swap(root->left,root->right);
//     exchange(root->left);
//     exchange(root->right);
// }

层序遍历


//层序遍历
void levelOrder(TreeNode *root)
{
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty())
    {
        TreeNode *t = q.front();
        q.pop();

        cout << t->val << ' ';
        if (t->left) q.push(t->left);
        if (t->right) q.push(t->right);
    }
}

查找先序遍历第k个数的值

//查找先序遍历中第K个数的值

//递归版本
int k = 2,n = 0;
char dgres = NULL;

void findK(TreeNode* root){
    if(!root) return;
    n++;
    if(n == k) dgres = root->val;
    dfs(root->left);
    dfs(root->right);
}

删除以X为根的子树的值


//删除以X为根的子树
//bfs
char x = 'C';
void dfsDelete(TreeNode* root){
    if(!root) return;
    if(root->val == x){
        root = NULL;
        return;
    }
    dfs(root->left);
    dfs(root->right);
}

求用孩子兄弟表示法存储的森林中，叶节点的总数
算法思想：在孩子兄弟表示法中，左指针代表自己的孩子，右指针代表父节点的兄弟孩子。因此若递归遍历到某节点无左指针，则代表该节点是叶节点。

//遍历用孩子兄弟表示法存储的森林的叶节点数

int leaves(TreeNode* root){
    if(!root) return 0;

    //如果该节点无左孩子，则代表无孩子，是叶节点
    if(!root->left) return ( 1 + leaves(root->right));
    else return (leaves(root->left) + leaves(root->right));

}

求孩子兄弟表示法存储的森林中所有树的最大高度

//递归算法求树的最大深度
int h = 1;
int mh;
void height(TreeNode* root){

    if(root->left){
        if(mh < ++h) mh = h;
        height(root->left);
    }
    if(root->right) height(root->right);
    h--;
}

部分完整代码

#include <bits/stdc++.h>
using namespace std;

//定义树节点结构体
struct TreeNode{
    char val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(char x, TreeNode *left, TreeNode *right) : val(x),left(left), right(right) {}
};


// 非递归求从下至上，从右至左的树的遍历
void invertLevelOrder(TreeNode* root){
    queue<TreeNode*> q;
    stack<TreeNode*> s;

    q.push(root);

    while(!q.empty()){
        auto t = q.front();
        q.pop();
        s.push(t);
        if(t->left) q.push(t->left);
        if(t->right) q.push(t->right);
    }

    while(!s.empty()){
        auto t = s.top();
        cout << t->val << ' ';
        s.pop();
    }
    cout << endl;
}

// 递归求树的高度
int heigh(TreeNode* root){
    if(!root) return 0;
    return max(heigh(root->left),heigh(root->right))+1;
}


//非递归求树的高度
int heigh2(TreeNode* root){

    int h = 0;
    queue<TreeNode*> q;
    q.push(root);

    while(!q.empty()){

        // 记录队列中的元素，也就是当前层的元素个数
        int n = q.size();

        while(n--){
            auto t = q.front();
            q.pop();
            if(t->left) q.push(t->left);
            if(t->right) q.push(t->right);
        }
        h++;
    }
    return h;
}


//求树的最大宽度
int width(TreeNode* root){

    //定义大根堆,用来存储每一层的宽度
    priority_queue<int> maxwidth;
    queue<TreeNode*> q;

    q.push(root);
    while(!q.empty()){

        int n = q.size();
        maxwidth.push(n);

        while(n--){
            auto t = q.front();
            q.pop();
            if(t->left) q.push(t->left);
            if(t->right) q.push(t->right);
        }
    }

    return maxwidth.top();
}

//求最近公共祖先
// 返回根结点到p的路径
vector<TreeNode *> findPath(TreeNode *root, TreeNode *p)
{
    vector<TreeNode*> s;
    TreeNode *cur = root, *pre = NULL;
    while (cur || s.size())
    {
        while (cur)
        {
            s.push_back(cur);
            cur = cur->left;
        }

        cur = s.back();
        if (cur->right && cur->right != pre)
            cur = cur->right;
        else
        {
            s.pop_back();
            if (cur == p)
                return s;
            pre = cur;
            cur = NULL;
        }
    }
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
    vector<TreeNode *> path1 = findPath(root, p);
    vector<TreeNode *> path2 = findPath(root, q);

    if (path1.size() > path2.size()) swap(path1, path2);
    for (int i = 0; i < path1.size(); i ++)
        if (path1[i] != path2[i])
            return path1[i - 1];
    return path1.back();
}


//判定是否是完全二叉树

/*
1. 如果某节点有右子树，无左子树，则不是完全二叉树
2. 如果这个节点左子树存在，但其左兄弟的右子树不存在，则不是完全二叉树；



*/


bool isCompleteTree(TreeNode* root){

    queue<TreeNode*> q;
    q.push(root);
    bool leaf = false;

    while(!q.empty()){

        auto t = q.front();
        q.pop();

        //如果遇到根节点
        if(t == NULL){
            leaf = true;
            continue;  // 跳过这层循环，直接进入下一层循环
        }

        if(leaf && t) return false;
        else{
            q.push(t->left);
            q.push(t->right);
        }
    }
    return true; 
}

//求双分支节点个数

int res = 0;

void dfs(TreeNode* root){
    if(!root) return;
    if(root->left && root->right) res++;
    if(root->left) dfs(root->left);
    if(root->right) dfs(root->right);
}


//交换左右子树
/*
基于后序遍历, [注]前序，后序遍历都可以实现，但中序遍历不可实现
*/
void exchange(TreeNode* root){
    if(!root) return; 
    exchange(root->left);
    exchange(root->right);
    swap(root->left,root->right);
}
/*
基于前序遍历的交换左右子树
*/
// void exchange(TreeNode* root){
//     if(!root) return; 
//     swap(root->left,root->right);
//     exchange(root->left);
//     exchange(root->right);
// }

//层序遍历
void levelOrder(TreeNode *root)
{
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty())
    {
        TreeNode *t = q.front();
        q.pop();

        cout << t->val << ' ';
        if (t->left) q.push(t->left);
        if (t->right) q.push(t->right);
    }
}

//查找先序遍历中第K个数的值

//递归版本
int k = 2,n = 0;
char dgres = NULL;

void findK(TreeNode* root){
    if(!root) return;
    n++;
    if(n == k) dgres = root->val;
    dfs(root->left);
    dfs(root->right);
}


//删除以X为根的子树
//bfs
char x = 'C';
void dfsDelete(TreeNode* root){
    if(!root) return;
    if(root->val == x){
        root = NULL;
        return;
    }
    dfs(root->left);
    dfs(root->right);
}

int main()
{
    TreeNode *root = new TreeNode('A',
                                  new TreeNode('B',
                                               new TreeNode('D'),
                                               new TreeNode('E')),
                                  new TreeNode('C',
                                               new TreeNode('F'),
                                               new TreeNode('G')));



    cout << "逆序树：";
    invertLevelOrder(root);

    cout << "递归求树的高度：";
    cout << heigh(root) << endl;;

    cout << "非递归求树的高度：";
    cout << heigh2(root) << endl;;

    cout << "树的最大宽度: ";
    cout << width(root) << endl;

    // cout << lowestCommonAncestor(root,'E','D');

    cout << "是否是完全二叉树?: ";
    cout << (isCompleteTree(root) ? "Yes" : "No") << endl;

    cout << "求双分支节点个数: ";
    dfs(root);
    cout << res << endl;

    cout << "交换左右子树后的层序遍历：";
    exchange(root);
    levelOrder(root);
    cout << endl;

    cout << "求先序遍历第K个节点的值(K=2): ";
    findK(root);
    cout << dgres << endl;

    cout << "求删除B的所有子树后的层序遍历 : "; 
    dfsDelete(root);
    levelOrder(root);
    cout <<endl;


    return 0;
}

0 评论