首页 > 编程语言 >代码随想录算法 - 二叉树5

代码随想录算法 - 二叉树5

时间:2024-09-14 20:35:49浏览次数:10  
标签:right return tmpNode 随想录 算法 二叉树 root 节点 left

题目1 530. 二叉搜索树的最小绝对差

给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值

差值是一个正数,其数值等于两值之差的绝对值。

示例 1:

img

输入:root = [4,2,6,1,3]
输出:1

示例 2:

img

输入:root = [1,0,48,null,null,12,49]
输出:1

提示:

  • 树中节点的数目范围是 [2, 104]
  • 0 <= Node.val <= 105

思路

最小绝对差实际上考察的就是按顺序排列的相邻元素的最小差值,因此对二叉搜索树使用中序遍历就能够找到相邻两元素,或者用递归按二叉搜索树的生成规则寻找相邻元素,我使用的是递归法。

递归法

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
       int lft = INT_MAX, rht = INT_MAX;
       if(!root->left && !root->right)
       {
            return INT_MAX;
       }
       TreeNode* tmpNode;
       if(root->left)
       {
            tmpNode = root->left;
            while(tmpNode->right)
            {
                tmpNode = tmpNode->right;
            }
            lft = min(abs(tmpNode->val - root->val), getMinimumDifference(root->left));
       }
       if(root->right)
       {
            tmpNode = root->right;
            while(tmpNode->left)
            {
                tmpNode = tmpNode->left;
            }
            rht = min(abs(tmpNode->val - root->val), getMinimumDifference(root->right));
       }
        return min(lft, rht);
    }
};

题目2 501. 二叉搜索树中的众数

给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。

如果树中有不止一个众数,可以按 任意顺序 返回。

假定 BST 满足如下定义:

  • 结点左子树中所含节点的值 小于等于 当前节点的值
  • 结点右子树中所含节点的值 大于等于 当前节点的值
  • 左子树和右子树都是二叉搜索树

示例 1:

img

输入:root = [1,null,2,2]
输出:[2]

示例 2:

输入:root = [0]
输出:[0]

提示:

  • 树中节点的数目在范围 [1, 104]
  • -105 <= Node.val <= 105

进阶:你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)

思路

用递归法中序遍历每一个节点,并比较每个元素的个数,最后得到结果。

代码

class Solution {
public:
    int max = INT_MIN;
    int curNum = 0;
    vector<int> result;
    TreeNode* preNode = nullptr;
    void search(TreeNode* root)
    {
        if(root->left)
            search(root->left);
        if(preNode && root->val != preNode->val)
        {
            curNum = 1;
        }
        else
        {
            curNum++;
        }
        if(curNum > max)
        {
            max = curNum;
            result.clear();
            result.push_back(root->val);
        }
        else if(curNum == max)
        {
            result.push_back(root->val);
        }
        preNode = root;
        if(root->right)
            search(root->right);
        return ;
    }
    vector<int> findMode(TreeNode* root) {
        search(root);
        return result;
    }
};

题目3 236. 二叉树的最近公共祖先*

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

示例 1:

img

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3
解释:节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2:

img

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出:5
解释:节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3:

输入:root = [1,2], p = 1, q = 2
输出:1

提示:

  • 树中节点数目在范围 [2, 105] 内。
  • -109 <= Node.val <= 109
  • 所有 Node.val 互不相同
  • p != q
  • pq 均存在于给定的二叉树中。

思路

用后续遍历可以保证parent节点是最后被访问的,因此,使用后序遍历将左子树和右子树遍历一遍找出目标p和q,最后推断出parent节点。

代码

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

        if(root->left && !root->right) return lowestCommonAncestor(root->left, p, q);
        if(!root->left && root->right) return lowestCommonAncestor(root->right, p, q);
        TreeNode* lftNode = lowestCommonAncestor(root->left, p, q),
                * rhtNode = lowestCommonAncestor(root->right, p, q);
        if(lftNode != nullptr && rhtNode != nullptr)
            return root;
        else if(lftNode && !rhtNode)
        {
            return lftNode;
        }
        else if(!lftNode && rhtNode)
        {
            return rhtNode;
        }
        return nullptr;
    }
};

标签:right,return,tmpNode,随想录,算法,二叉树,root,节点,left
From: https://www.cnblogs.com/code4log/p/18414651

相关文章

  • 【算法笔记】线性基
    线性基定义:给定数集\(s\),以异或运算张成的数集与\(S\)相同的极大线性无关集,称为原数集的一个线性基。性质:原数集的任意一个数都能有线性基内部的一些数异或得到。线性基内部任意数异或不为0线性基内数唯一,且保证性质一的情况下,数的个数最少。线性基内每个数的最高有效位......
  • 滑动窗口算法—最小覆盖子串
    题目         ”最小覆盖子串“问题,难度为Hard,题目如下:        给你两个字符串S和T,请你在S中找到包含T中全部字母的最短子串。如果S中没有这样一个子串,则算法返回空串,如果存在这样一个子串,则可以认为答案是唯一的。    比如输入S="ADB......
  • java计算机毕业设计协同过滤算法的就业推荐系统(开题+程序+论文)
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景在当今快速发展的数字经济时代,人才与企业的精准匹配成为推动产业升级与创新的关键。然而,面对海量的人才信息与多样化的岗位需求,传统的招聘方式往往效......
  • 前端必须掌握的五种排序算法,你会几种?
    文章目录前言1.冒泡排序(BubbleSort)2.选择排序(SelectionSort)3.插入排序(InsertionSort)4.快速排序(QuickSort)5.归并排序(MergeSort)前言在前端开发中,对数据进行排序是一项基本且常见的任务。掌握排序算法不仅可以帮助我们更有效地处理数据,还能提升代码的执行效......
  • 代码随想录算法 - 二叉树4
    题目1654.最大二叉树给定一个不重复的整数数组nums。最大二叉树可以用下面的算法从nums递归地构建:创建一个根节点,其值为nums中的最大值。递归地在最大值左边的子数组前缀上构建左子树。递归地在最大值右边的子数组后缀上构建右子树。返回nums构建的*......
  • dfs 验证搜索二叉树——leetcode98
    代码来自leetcode官方一开始我自己写这个代码时只注意当前节点是否会存在空指针,并没有注意到他的孩子节点也有可能为空,绕了我好久。。。。。。/***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNode*left;*TreeNode*right;......
  • 顶刊算法 | 鹈鹕算法POA-Transformer-LSTM多变量回归预测
    顶刊算法|鹈鹕算法POA-Transformer-LSTM多变量回归预测目录顶刊算法|鹈鹕算法POA-Transformer-LSTM多变量回归预测效果一览基本介绍程序设计参考资料效果一览基本介绍1.Matlab实现顶刊算法|鹈鹕算法POA-Transformer-LSTM多变量回归预测(程序可以作为JCR一区级论文代码支撑,目......
  • 路径规划 | 基于A*算法的往返式全覆盖路径规划的改进算法(Matlab)
    目录效果一览基本介绍程序设计参考文献效果一览基本介绍基于A*算法的往返式全覆盖路径规划的改进算法matlab实现代码往返式全覆盖路径规划,通过建立二维栅格地图,设置障碍物,以及起始点根据定义往返式路径规划的定义的优先级运动规则从起始点开始进行全图遍历,利用A星算法逃离死角......
  • 多输入多输出 | Matlab实现SO-BP蛇群算法优化BP神经网络多输入多输出预测
    多输入多输出|Matlab实现SO-BP蛇群算法优化BP神经网络多输入多输出预测目录多输入多输出|Matlab实现SO-BP蛇群算法优化BP神经网络多输入多输出预测预测效果基本介绍程序设计往期精彩参考资料预测效果基本介绍多输入多输出|Matlab实现SO-BP蛇群算法优化BP神经网络多输入多输......
  • 时序预测 | MATLAB实现BKA-XGBoost(黑翅鸢优化算法优化极限梯度提升树)时间序列预测
    时序预测|MATLAB实现BKA-XGBoost(黑翅鸢优化算法优化极限梯度提升树)时间序列预测目录时序预测|MATLAB实现BKA-XGBoost(黑翅鸢优化算法优化极限梯度提升树)时间序列预测预测效果基本介绍模型描述程序设计参考资料预测效果基本介绍Matlab实现BKA-XGBoost时间序列预测,黑翅鸢优......