首页 > 其他分享 >day018二叉树

day018二叉树

时间:2024-08-03 19:55:51浏览次数:16  
标签:TreeNode travelRoot res day018 二叉树 return root 节点

530.二叉树的最小绝对差

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

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

 思路:此题与昨天的验证二叉搜索树很像,同样是中序遍历将二叉树节点按照顺序加入到动态数组中,随后遍历动态数组,维护一个相邻的最小差值即可。

class Solution {
public:
    void travelRoot(TreeNode* root,vector<int>& res){
        if(root==nullptr){
            return ;
        }
        travelRoot(root->left,res);
        res.push_back(root->val);
        travelRoot(root->right,res);
    }
public:
    int getMinimumDifference(TreeNode* root) {
        vector<int> res;
        travelRoot(root,res);
        int minNum=INT_MAX;
        for(int i=1;i<res.size();i++){
            int num=res[i]-res[i-1];
            if(num<minNum){
                minNum=num;
            }
        } 
        return minNum;
    }
};

501.二叉搜索树中的众数

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

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

假定 BST 满足如下定义:

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

 思路:我感觉二叉搜索树的题目好像大多数都可以这么做,就是有关节点值或他们之间的关系之类的,都可以将二叉树的节点的值按照中序遍历,有序的放入数组中。然后在通过这个动态数组来解决题目。易错点:我在主函数放入动态数组中的时候忘记,当出现次数大于当前数的时候要将动态数组置为空,因为直接替换掉了。

class Solution {
public:
    void travelRoot(TreeNode* root,vector<int>& res){
        if(root==nullptr){
            return ;   
        }
        travelRoot(root->left,res);
        res.push_back(root->val);
        travelRoot(root->right,res);
        return ;
    }
public:
    vector<int> findMode(TreeNode* root) {
        vector<int> res;
        travelRoot(root,res);
        unordered_map<int,int> mp;
        for(int i:res){
            mp[i]++;
        }
        vector<int> vec;
        int count=0;
        for(auto& j:mp){
            if(j.second>count){
                vec.clear();//*** 因为当前的值比它大所以要清空
                vec.push_back(j.first);
                count=j.second;
            }else if(j.second==count){
                vec.push_back(j.first);
            }
        }
        return vec;
    }
};

236.二叉树的最近公共祖先

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

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

 思路:首先要理解公共祖先的概念,然后,这道题的思路是递归,深度优先遍历二叉树中的每个节点,当找到qp节点就返回给上一层,(定义两个节点用于存储)然后判断这两个节点是否为空,若不为空代表找到了p或q的值,判断,如果左右都不为空,返回当前的根节点即可,如下图左侧的情况,若左为空右不为空,代表右子树遇到了pq,返回right。如下图右侧,左不为空 右为空同理。

class Solution {
public:
    TreeNode* travelRoot(TreeNode* root, TreeNode* p, TreeNode* q){
        if(root==nullptr){
            return nullptr;
        }
        if(root==p||root==q){
            return root;
        }
        TreeNode* left=travelRoot(root->left,p,q);//左子树有没有出现q和p
        TreeNode* right=travelRoot(root->right,p,q);//右

        if(left!=nullptr&&right!=nullptr){//说明左子树或右子树的左右节点存在q和p
            return root;
        }
        if(left==nullptr&&right!=nullptr){
            return right;
        }
        if(left!=nullptr&&right==nullptr){
            return left;
        }
        else return nullptr;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* node=travelRoot(root,p,q);
        return node;
    }
};

标签:TreeNode,travelRoot,res,day018,二叉树,return,root,节点
From: https://blog.csdn.net/m0_62956971/article/details/140886190

相关文章

  • day014(二叉树章节)+北境互娱游戏开发一面
    222.完全二叉树节点的个数给你一棵完全二叉树的根节点root,求出该树的节点个数。完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第h层,则该层包含1~ 2h 个......
  • 二叉树链式结构代码讲解与实现
    本片将续之前的文章二叉树的概念进行二叉树基本操作的实现,二叉树oj题将在下篇文章讲解。目录a.创建二叉树代码:一、二叉树的遍历1.1前序、中序以及后序遍历代码:如图:(前序遍历递归图解)测试代码:二、节点个数以及高度2.1 二叉树节点个数思想:要求二叉树的总节点个数,左......
  • 【数据结构】二叉树和堆
     一、二叉树1.二叉树的基本概念在C语言中,二叉树是一种基础的数据结构,它由节点组成,每个节点包含数据元素以及指向其他节点的指针。下面是二叉树的基本概念以及如何在C语言中表示和操作它。节点(Node):二叉树的每个元素称为节点,每个节点都有一个数据域和两个指针域,通常称为左指......
  • 代码随想录算法训练营Day18 | Leetcode 530 二叉搜索树的最小绝对差 Leetcode 236 二
    前言今天有一道题目没写,二叉搜索树中的众数,有点太难理解了,先放一放。Leetcode530二叉搜索树的最小绝对差题目链接:530.二叉搜索树的最小绝对差-力扣(LeetCode)代码随想录题解:代码随想录(programmercarl.com)思路:二叉搜索树的性质是中序遍历为升序的,所以我们想找最小绝......
  • Day18 二叉树Part6
    目录任务530.二叉搜索树的最小绝对差思路501.二叉搜索树中的众数思路236.二叉树的最近公共祖先思路心得体会任务530.二叉搜索树的最小绝对差给你一个二叉搜索树的根节点root,返回树中任意两不同节点值之间的最小差值。差值是一个正数,其数值等于两值之差的绝对值。思路......
  • 先(后)序遍历确定唯一二叉树
    在二叉树的先序遍历或后序遍历序列中,如果我们记录了空节点的位置(通常用特殊符号如'#'表示),就足以唯一确定一棵二叉树的结构。这种方法的关键在于,记录空节点的位置能够帮助我们在遍历序列中准确地还原出树中节点的结构信息。因此,只要给出了先序遍历或后序遍历序列以及空节点的位置,......
  • 数据结构--------二叉树的定义及遍历操作的实现
    /*二叉树的链式存储以及基本操作*/#include<stdio.h>#include<stdlib.h>//树的节点typedefstructBTNode{intdata;structBTNode*lchild;structBTNode*rchild;}BTNode,*BTTree;/......
  • 【代码随想录训练营第42期 Day17打卡 二叉树Part5-LeetCode 654.最大二叉树 617.合并
    目录一、做题心得二、题目与题解题目一:654.最大二叉树题目链接题解:递归题目二:617.合并二叉树题目链接题解:递归(前序遍历)题目三:617.合并二叉树题目链接题解:BFS层序遍历 题目四:98.验证二叉搜索树题目链接题解:递归(中序遍历)三、小结一、做题心得今天是代码随想......
  • Day17 二叉树Part5
    目录任务654.最大二叉树思路617.合并二叉树思路700.二叉搜索树中的搜索思路98.验证二叉搜索树思路(错误)思路(正确)心得体会任务654.最大二叉树给定一个不重复的整数数组nums。最大二叉树可以用下面的算法从nums递归地构建:创建一个根节点,其值为nums中的最大值。递归......
  • 代码随想录day17 || 654 最大二叉树,617 合并二叉树,700 二叉搜索树搜索,98 验证二叉搜索
    645最大二叉树funcconstructMaximumBinaryTree(nums[]int)*TreeNode{ //思路,算法思路基本等同于通过中序前序构造二叉树 //1,取最大值作为根节点 //2,切割数组 //3,递归左右子树 iflen(nums)==0{ returnnil } //切割数组取最大值 max,left,right:=......