程序员经验分享-hwhale

c++ 数据结构——树

2023-11-08

1.树概念：

暂略。

2.树的相关题目：

2.1 leetcode 104 —— Maximum Depth of Binary Tree 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root)
        {
            return 0;
        }
        if(!root->left && !root->right)//如果根没有孩子了
        {
            return 1;
        }
        else
        {
            int lHeight = maxDepth(root->left);
            int rHeight = maxDepth(root->right);
            return max(lHeight,rHeight) + 1;
        }
    }
};

2.2 ***leetcode 108 —— Convert Sorted Array to Binary Search Tree 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.empty())
        {
            return NULL;
        }
        return sorted(nums,0,nums.size()-1);
    }
    TreeNode* sorted(vector<int> nums, int start, int end)
    {   
        if(start > end)
        {
            return NULL;
        }
        else if(start == end)
        {
            TreeNode* tmp = new TreeNode(nums[start]);
            return tmp;
        }
        else
        {
            int curr = start + (end - start) / 2;
            TreeNode* tmp = new TreeNode(nums[curr]);
            tmp->left = sorted(nums, start, curr - 1);
            tmp->right = sorted(nums, curr + 1, end);
            return tmp;
        }    
        
    }
};

2.3 ***leetcode 101 —— Symmetric Tree 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root || (!root->left)&&(!root->right))
        {
            return true;
        }
        if(!root->left || !root->right)
        {
            return false;
        }
        TreeNode* left_tmp;
        TreeNode* right_tmp;
        queue<TreeNode*> left_nodes;
        queue<TreeNode*> right_nodes;
        
        left_nodes.push(root->left);
        right_nodes.push(root->right);
        
        while(!left_nodes.empty() && !right_nodes.empty())
        {
            left_tmp = left_nodes.front();
            right_tmp = right_nodes.front();
            if(left_tmp->val == right_tmp->val)
            {               
                if((!left_tmp->left && right_tmp->right) || (left_tmp->left && !right_tmp->right))
                {
                    break;
                }
                else if(left_tmp->left && right_tmp->right)
                {
                    left_nodes.push(left_tmp->left);
                    right_nodes.push(right_tmp->right);
                }
                
                if((!left_tmp->right && right_tmp->left) || (left_tmp->right && !right_tmp->left))
                {
                    break;
                }
                else if(left_tmp->right && right_tmp->left)
                {
                    left_nodes.push(left_tmp->right);
                    right_nodes.push(right_tmp->left);
                }                            
                left_nodes.pop();
                right_nodes.pop();
            }
            else
            {
                break;
            }
            
        }
        if(left_nodes.empty() && right_nodes.empty())
        {
            return true;
        }
        return false;
    }
};

2.4 ***leetcode 94 —— Binary Tree Inorder Traversal

递归解决：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        inorder(root,result);
        return result;
    }
    
    void inorder(TreeNode* root, vector<int> &result)
    {
        if(root != NULL)
        {
        inorder(root->left,result);
        result.push_back(root->val);
        inorder(root->right,result);
        }
    }    
};

栈解决（其实思路和递归一样）：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> toTraversal;
        vector<int> result;
        while(root != NULL || !toTraversal.empty())
        {
            //遍历左节点
            while(root != NULL)
            {
                toTraversal.push(root);
                root = root->left;
            }
            root = toTraversal.top();
            result.push_back(root->val);
            toTraversal.pop();
            root = root->right;
        }
        return result;
    }
   
};

2.5 ***leetcode 230 —— Kth Smallest Element in a BST

递归：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        vector<int> list;
        findKth(root,k,list);
        return list[k-1];
    }
    void findKth(TreeNode* root,int k,vector<int> &list)
    {
        if(root != NULL)
        {
            findKth(root->left,k,list);
            list.push_back(root->val);
            if(list.size() == k)
            {
                return;
            }
            findKth(root->right,k,list);
        }
    }
};

迭代：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        vector<int> res;
        stack<TreeNode*> ss;
        TreeNode* top;
        while(root || !ss.empty())
        {
            while(root)
            {
                ss.push(root);
                root = root->left;
            }
            root = ss.top();
            res.push_back(root->val);
            ss.pop();
            if(res.size() == k)
            {
                break;
            }
            root = root->right;            
        }
        return res[k-1];
            
    }
};

2.6 ***leetcode 105 —— Construct Binary Tree from Preorder and Inorder Traversal 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int pos = 0;
        
        return build(preorder, inorder, 0, inorder.size(),pos);
    }
    TreeNode* build(vector<int> &preorder, vector<int> &inorder,int begin,int end,int &pos)
    {
        if(begin>=end || pos >= preorder.size() )
        {
            return NULL;
        }
        TreeNode *root = new TreeNode(preorder[pos++]);
        int cur = begin;
        while(root->val != inorder[cur])
        {
            cur++;
        }
        root->left = build(preorder, inorder, begin, cur, pos);
        root->right = build(preorder, inorder, cur+1, end, pos);
        
        return root;
    }
};

2.7 leetcode 102 —— Binary Tree Level Order Traversal 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(!root)
        {
            return res;   
        }
        vector<int> tmp;
        
        queue<TreeNode*> odd;
        queue<TreeNode*> even;
        
        even.push(root);
        tmp.push_back(root->val);
        res.push_back(tmp);
        
        int count = 1;
        
        while(!even.empty() || !odd.empty())
        {
            vector<int> tmp;
            if(count % 2 == 0)
            {
                while(!odd.empty())
                {
                    if(odd.front()->left)
                    {
                        even.push(odd.front()->left);
                        tmp.push_back(odd.front()->left->val);
                    }
                    if(odd.front()->right)
                    {
                        even.push(odd.front()->right);
                        tmp.push_back(odd.front()->right->val);
                    }
                    odd.pop();
                }
                if(tmp.size())
                {
                    res.push_back(tmp);
                }
                count++;
            }
            else
            {
                while(!even.empty())
                {
                    if(even.front()->left)
                    {
                        odd.push(even.front()->left);
                        tmp.push_back(even.front()->left->val);
                    }
                    if(even.front()->right)
                    {
                        odd.push(even.front()->right);
                        tmp.push_back(even.front()->right->val);
                    }
                    even.pop();
                }
                if(tmp.size())
                {
                    res.push_back(tmp);
                }
                count++;
            }
        }
        
        return res;
    }
};

2.8 ***leetcode 236 —— Lowest Common Ancestor of a Binary Tree 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        find(root , p, q);
        return ans;
    }
    bool find(TreeNode* root, TreeNode* p, TreeNode * q)
    {
        if(root == NULL)
        {
            return false;
        }
        
        bool left = find(root->left, p, q) ? 1 : 0;
        bool right = find(root->right, p, q) ? 1 : 0;        
        bool mid = (root == p || root == q) ? 1 : 0;
        
        if(left+right+mid > 1 && !ans)
        {
            ans = root;
        }
        
        return left+right+mid;
    }
private: TreeNode* ans;    
};

2.9 leetcode 116 —— Populating Next Right Pointers in Each Node 

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() {}

    Node(int _val, Node* _left, Node* _right, Node* _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        
        if(!root) return NULL;
        
        queue<Node*> odd;
        queue<Node*> even;
        int layer = 0;
        even.push(root);
        Node* tmp;
        while(!odd.empty() || !even.empty())
        {
            while((layer + 1) % 2 && !even.empty()) //下一层为奇数层
            {
                tmp = even.front();
                if(tmp->left) odd.push(tmp->left);
                if(tmp->right) odd.push(tmp->right);
                even.pop();
                if(!even.empty()) tmp->next = even.front();
                else 
                {
                    layer++;
                    continue;
                }
            }
            
            while((layer + 1) % 2 == 0 && !odd.empty())
            {
                tmp = odd.front();
                if(tmp->left) even.push(tmp->left);
                if(tmp->right) even.push(tmp->right);
                odd.pop();
                if(!odd.empty()) tmp->next = odd.front();
                else 
                {
                    layer++;
                    continue;
                }
            }
        }
        return root;
    }
    
};

2.10 ***leetcode 98 —— Validate Binary Search Tree 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        
        return isValid(root, NULL, NULL);
    }
    bool isValid(TreeNode* root, TreeNode* upper, TreeNode* lowwer){
        if(!root)
        {
            return true;
        }
        
        if(upper && root->val >= upper->val) return false;
        if(lowwer && root->val <= lowwer->val) return false;
        
        if(!isValid(root->left, root, lowwer)) return false;
        if(!isValid(root->right,upper, root)) return false;
        
        return true;
    }             

};

2.11 leetcode 617 —— Merge Two Binary Trees 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(!t1 && !t2)
        {
            return NULL;
        }
        
        if(!t1 && t2)
        {
            return t2;
        }
        
        if(t1 && !t2)
        {
            return t1;
        }
        
        t1->val += t2->val;
        t1->left = mergeTrees(t1->left, t2->left);
        t1->right = mergeTrees(t1->right, t2->right);
        
        return t1;
        
    }
};

2.12 leetcode 226 —— Invert Binary Tree 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root)
        {
            return NULL;
        }
        
        TreeNode* tmp = root->left;
        root->left = invertTree(root->right);
        root->right = invertTree(tmp);
        
        return root;
    }
};

 

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

leetcode刷题笔记

c++ 数据结构——树 的相关文章

  • 打印机错误0x00000bc4的解决办法

    共享打印机在使用过程中难免会出现一些问题 比如连接共享打印机错误 提示代码0x00000bc4 这该如何解决 共享打印机出现问题是件非常麻烦的事 下面就来看看小编整理的解决办法吧 Win11连接共享打印机错误0x00000bc4解决方法 1

随机推荐

  • RabbitMQ：work结构

    gt 只需要在消费者端 添加Qos能力以及更改为手动ack即可让消费者 根据自己的能力去消费指定的消息 而不是默认情况下由RabbitMQ平均分配了 生产者不变 正常发布消息到默认的exchange gt 消费者指定Qoa和手动ack 生产

  • 2023Web前端面试题及答案（一）

    答案仅供参考 每人的理解不一样 文章目录 1 简单说一说事件流原理 事件流 1 事件流是指页面 接收事件的顺序 2 假设页面中的元素都具备相同的事件 并且这些个元素之间是相互嵌套的 关系 3 那么在触发一个元素的事件时候 会触发其他的元素

  • 华为od机考真题-HJ105-记负均正II（较难）

    非负数缓存 data lst 负数个数 count 0 while 1 try data int input if data gt 0 data lst append

  • 卷积核大小不一样的卷积

    这种不是33而是51的 参考这个https blog csdn net qq 37541097 article details 102926037 也就是说把中间写成 3 5 就可以了

  • Open3D：Win10 + VS2017配置Open3D（C++、python）

    累了就要打游戏 2020 08 25 15 13 10 3350 收藏 25 分类专栏 Open3D 文章标签 点云 Open3D C 版权 Open3D 专栏收录该内容 5 篇文章1 订阅 订阅专栏 20200825 今天七夕 呱呱呱 O

  • 苹果开发者账号申请教程

    只有苹果开发者账号才能上架App Store 苹果开发者需要年费 是苹果公司收的 公司 政府和企业账号申请比较复杂 如果不想麻烦 或没有visa银行卡 可以联系他们技术代申请 如果只是安装ios应用到自己手机测试 现在只需要注册一个普通的苹

  • CSDN自带编辑器语法

    这里写自定义目录标题 欢迎使用Markdown编辑器 新的改变 功能快捷键 合理的创建标题 有助于目录的生成 如何改变文本的样式 插入链接与图片 如何插入一段漂亮的代码片 生成一个适合你的列表 创建一个表格 设定内容居中 居左 居右 Sma

  • FlatBuffers使用简介

    tools flatbuffers opensource 概述 Google在今年6月份发布了跨平台序列化工具FlatBuffers 提供了C Java Go C 接口支持 这是一个注重性能和资源使用的序列化类库 相较于Protocol B

  • POI高级使用法则

    各位兄台 想必经过昨日好梦 早已精神饱满 请允许小编接听上回 讲解POI进阶功法 昨日奇闻 POI搞定电子表格 我们经过昨日的学习 懂得了POI基本的读写操作 今日让我们进一步看一下POI的高级使用方法 壹 我们知道对于Excel是含有03

  • 论文笔记：Mystique: Efficient Conversions for Zero-Knowledge Proofs with Applications to Machine Learnin

    论文笔记 Mystique Efficient Conversions for Zero Knowledge Proofs with Applications to Machine Learning 论文介绍 ZK在人工智能上的应用讨论 现

  • Sqlite3 导出/导入SQL语句

    前言 Sqlite3 提供了较轻便的数据库操作 速度非常快 也比较稳定 在嵌入式产品中用的非常广泛 但嵌入式产品往往由于不稳定性因素非常多 备份是必不可少的 直接拷贝 db 文件并不是太好的主意 所以引出本文所要讲的主题 Sqlite3 导

  • QAC的CLI 转载文章

    2 静态分析执行 为了方便后续将鸿蒙的静态分析过程部署到持续集成平台上 本文以命令行的方式进行静态分析操作的演示 具体步骤如下 创建QAC工程 命令如下 qacli admin qaf project config qaf project

  • pycharm编写的时候出现的提示框如何关闭

    pycharm编写的时候出现的提示框如何关闭 问题描述 pycharm编写的时候出现的提示框如何关闭 问题原因 错误分析 这个要去Pycharm的 setting里面设置一下 解决方法 pycharm提示框关闭方法 点击settings进入

  • Python描述符（descriptor）解密 属性（property）、以及装饰器（decorator）

    Python描述符 descriptor 解密 慕容老匹夫 2014 年 3 月 27 日 1 条评论 标签 descriptor Python 描述符 25 本文由 极客范 慕容老匹夫 翻译自 Chris Beaumont 欢迎加入极客翻

  • 计算机考研复试汇总

    一 中英文面试 1 为什么考研究生呢 why do you take the postguaduate entrance exanmination 我认为有一下几点 第一 我的本科专业就是计算机科学与技术 已经学习了4年计算机培养出浓厚的兴

  • ES6解构

    ES6解构 1 解构对象案例 var obj a 1 b 2 const a b obj console log a 1 console log b 2 var obj a 1 b 2 const c b obj console log c

  • 机器学习之CART树

    CART树 1 Cart树介绍 2 Cart树生成 3 回归树 4 分类树 4 1 分类树原理 4 2 分类树算法步骤 4 3 案例 5 Cart树总结 1 Cart树介绍 分类回归树 CART Classification And Reg

  • 吃饭睡觉打豆豆

    哈哈哈

  • Python: for 循环

    一 For 语法结构和基于数字 range 的循环 for x in range 5 print hello 二 基于列表list 元组tuple的循环 numbers1 1 2 3 4 5 numbers2 6 7 2 5 name zh

  • c++ 数据结构——树

    1 树概念 暂略 2 树的相关题目 2 1 leetcode 104 Maximum Depth of Binary Tree Definition for a binary tree node struct TreeNode int va

热门标签