IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 专题复习:二叉树(3) -> 正文阅读

[数据结构与算法]专题复习:二叉树(3)

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

对于二叉搜索树而言,因为其特殊的结构,即左子树的值均小于root的值,右子树的值均大于root的值,因此,对于二叉搜索树的最近公共祖先比较好确定。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return root;

        if(p->val == root->val || q->val == root->val)//如果p和q其中一个等于root 那么root即为最近公共祖先
        {
            return root;
        }
        if(p->val < root->val && q->val < root->val)// 如果p和q的值都小于root的值那么去root的左子树去寻找
        {
            return lowestCommonAncestor(root->left, p, q);
        }
        else if(p->val > root->val && q->val > root->val)// 如果p和q的值都大于root的值那么去root的右边子树去寻找
        {
            return lowestCommonAncestor(root->right, p, q);
        }
        else //此时说明 p和q位于root的左右两侧
        {
            return root;
        }
        
    }
};

剑指 Offer 68 - II. 二叉树的最近公共祖先

二叉树不像二叉搜索树那样结构与数值大小强相关。因此,不同通过判断p->val q->val和root->val的值的关系去选择去root->left或者root->right找最近公共祖先,只能分别试着去root->left或者root->right找最近公共祖先,如果其中一个为空,则返回另一个,如果两个都为空 返回空,如果两个均不为空,那么返回此时的root

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return root;
        if(p->val == root->val || q->val == root->val) return root;
        TreeNode *left = lowestCommonAncestor(root->left, p, q); 
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if(!left) return right;
        else if(!right) return left;
        else return root;
    }
};

leetcode?662. 二叉树最大宽度

思路:利用满二叉树? BFS

?我们可以把这些值存在原来的节点中,也可以新建一个map来保存这些值。

并利用双端队列deque

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if(!root) return 0;
        int len = 0;
        deque<TreeNode*> a;
        root->val = 1;
        a.push_back(root);

        while(!a.empty())
        {
            int size = a.size();
            len = max(len, a.back()->val - a.front()->val + 1);
            // 编号缩小的差值
            int offset = a.front()->val;//为了防止节点中的val过大
                                        //二叉树中每一行的第一个节点中的值,作为参考值 去计算后面节点的值
            while(size--)
            {
                TreeNode* temp = a.front();
                temp->val -= offset;
                a.pop_front();
                if(temp->left)
                {
                    a.push_back(temp->left);
                    temp->left->val = 2 * temp->val;
                }
                if(temp->right)
                {
                    a.push_back(temp->right);
                    temp->right->val = 2 * temp->val + 1;
                }
                
            }
        }
        return len;
    }
};

剑指 Offer 54. 二叉搜索树的第k大节点

思路:采用右--中--左的遍历方式

注意:count++之后立即进行判断是否是第k大的数? count记录第count个大的值

class Solution {
    int res = 0;
    void dfs(TreeNode* root, int k, int &count)
    {
        if(!root) return;       
        if(root->right) dfs(root->right, k, count);
        count++;
        if(count == k) 
        {
            res = root->val;
            return;
        }
        if(root->left) dfs(root->left,k, count);      
    }
public:
    int kthLargest(TreeNode* root, int k) {
        if(!root) return 0;
        int count = 0;
        dfs(root, k, count);
        return res;
    }
};

leetcode?230. 二叉搜索树中第K小的元素

思路:同上

class Solution {

    int res = 0;
    void dfs(TreeNode* root, int k, int& count)
    {
        if(!root) return;
        dfs(root->left, k , count);
        count++;
        if(count == k)
        {
            res = root->val;
            return;
        }
        dfs(root->right, k , count);
    }
public:
    int kthSmallest(TreeNode* root, int k) {
        if(!root) return 0;
        int count = 0;
        dfs(root, k ,count);
        return res;
    }
};

剑指 Offer 55 - II. 平衡二叉树

思路:根据求二叉树的最大深度 只需要加个比较 left和right的差值

class Solution {
    bool res = true;
    int dfs(TreeNode *root)
    {
        if(!root) return 0;
        int left = dfs(root->left);
        int right = dfs(root->right);
        if(abs(left - right) > 1)
        {
            res = false;
            return 0;
        }
        return max(left, right) + 1;
    }
public:
    bool isBalanced(TreeNode* root) {
        dfs(root);
        return res;
    }
};

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-07-25 11:55:27  更:2021-07-25 11:56:54 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 17:52:16-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码