二叉树OJ题(C++实现)

这篇具有很好参考价值的文章主要介绍了二叉树OJ题(C++实现)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.二叉树的层序遍历

二叉树的层序遍历 OJ连接

二叉树OJ题(C++实现)

主要思路是借助一个队列,将每一层的数据以size统计,当size为0时说明该层数据已经输入完,将这一层的数据传入vector中,再通过push_back 传入 vector< vector< int >中


二叉树OJ题(C++实现)
class Solution {
public:
   
    string tree2str(TreeNode* root) {
      
        if(root==NULL)
        {
            return "";
        }
         string s;
        //to_string 将任意类型转换为字符串
         s=to_string(root->val);
         //只有左右子树都为空时 左子树才不加括号
        if(root->left==NULL&&root->right==NULL)
        {
             //;
        }
        else 
        {
        s+='(';
        s+= tree2str(root->left);
        s+=')';
        }
        //若右子树为空 ,则不加括号
     if(root->right!=NULL)
     {
         s+='(';
         s+=  tree2str(root->right);
         s+=')';
     }
        return s;
    }
};

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

二叉树的最近公共祖先OJ连接


二叉树OJ题(C++实现)

共分为三种情况

第一种情况

二叉树OJ题(C++实现)

寻找节点7与0的公共祖先为 根节点3
节点7在根的左子树,而节点0在根的右子树

若一个在根的左子树,一个在根的右子树 , 则根就为公共祖先


第二种情况
以左子树为例

二叉树OJ题(C++实现)

节点7与节点4属于根的左子树
节点7与节点4的最近公共祖先为 他们共同的父节点2


二叉树OJ题(C++实现)
若两个节点都在根的左子树,则递归根的左子树的节点为根,判断两个节点是否为根的左右子树,直到寻找到


第三种情况
二叉树OJ题(C++实现)

节点5与节点4的最近公共祖先是节点5
节点5与节点4都属于根的左子树
若两个节点都在根的左子树,则递归根的左子树的节点为根,当这个根为两个节点其中一个时,则这个节点就为公共祖先


由于第二种和第三种情况,节点都在左子树上,所以可以看作是一种情况


class Solution {
public:
bool istree(TreeNode*root,TreeNode*x)
{
      if(root==NULL)
      {
          return false;
      }
      if(root==x)
      {
          return true;
      }
      return istree(root->left,x)|| istree(root->right,x);
}
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
          if(root==NULL)
          {
              return NULL;
          }
          //若p/q节点有一个节点为根节点,则最近公共祖先为根节点
          if(p==root||q==root)
          {
              return root;
          }
          
           bool pleft=istree(root->left,p);
           bool pright=!pleft;
           bool qleft=istree(root->left,q);
           bool qright=!qleft;
           //两个节点分别在左右子树上
           if( (pleft&&qright)|| (pright&&qleft))
           {
               return root;
           }
           //两个节点都在根的左子树上,则递归左子树
           else if(pleft&&qleft)
           {
                return lowestCommonAncestor(root->left,p,q);
           }
           //两个节点都在根的右子树上,则递归右子树
           else 
           {
              return lowestCommonAncestor(root->right,p,q);
           }
    }
};

3.二叉搜索树与双向链表

二叉搜索树与双向链表OJ连接

二叉树OJ题(C++实现)

prev节点用于记录cur节点的上一个

二叉树OJ题(C++实现)

当cur节点值为4时,prev=NULL,因为4属于双向链表第一个节点值 所以没必要链接
只需更新prev的值为cur值即可


二叉树OJ题(C++实现)

prev值不为空时,将cur节点与prev节点进行连接,并更新prev节点值
prev->right=cur
cur->left=prev


class Solution {
  public:
  void inconvert(TreeNode*cur,TreeNode*&prev)
  //因为prev是要跟着cur进行变化的,所以使用引用
  {
	if(cur==nullptr)
	return ;
	inconvert(cur->left,prev);
	//cur出现的顺序就为中序
	if(prev)
	{
		prev->right=cur;
		cur->left=prev;
	}
	prev=cur;

	inconvert(cur->right,prev);

  }
    TreeNode* Convert(TreeNode* root) {
		TreeNode*prev=nullptr;//记录cur节点的上一个
       inconvert(root,prev);
	    TreeNode*head=root;
		//通过遍历左子树的方式找到第一个节点
		while(head&&head->left)
		{
			head=head->left;
		}
		return head;
    }
};


4.从前序与中序遍历序列构造二叉树


从前序与中序遍历序列构造二叉树OJ链接


二叉树OJ题(C++实现)二叉树OJ题(C++实现)
二叉树OJ题(C++实现)

创建root,并确定值为3
在中序数组中寻找 root值为3的节点 ,并标记其下标为rooti
再通过递归的方式分别创建root的left与root的right


二叉树OJ题(C++实现)

同时每次都需要prev++,来确定新的根,
每次rooti都被赋值为inbegin,是为了中序数组的新区间内寻找到根


递归结束的判断条件

二叉树OJ题(C++实现)

若rooti与inbegin都为数组中第一个数的下标时,
[inbegin, rooti-1] 即 [ 0,-1] 为不存在的区间
所以当 inbegin >inright时,就直接返回
文章来源地址https://www.toymoban.com/news/detail-427094.html


class Solution {
public:
//prev为先序数组的下标
//inbeing与inend为 左右子树分割区间
    TreeNode*istree(vector<int>& preorder, vector<int>& inorder,int &prev,
    int inbegin,int inend)
    {
        //若rooti值与inbegin同时为第一个值,
        //则 [inegin,rooti-1]即 [0 ,-1]会报错
        if(inbegin>inend)
        {
            return nullptr;
        }
        //通过先序创建根节点
        TreeNode*root=new TreeNode();
        root->val=preorder[prev];
        //在中序数组中查找root对应的值
        int rooti=inbegin;
        while(rooti<=inend)
        {
            if(preorder[prev]==inorder[rooti])
            {
                break;
            }
            rooti++;
        }
        prev++;//由于是引用,前序的根也要跟着变化
        //分割左右子树区间
      // [inbegin rooti-1] rooti [rooti+1 inend]
        
      root->left=istree(preorder,inorder,prev,inbegin,rooti-1);
      root->right=istree(preorder,inorder,prev,rooti+1,inend);
      return root;


    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i=0;
           return  istree(preorder,inorder,i,0,inorder.size()-1);
    }
};

到了这里,关于二叉树OJ题(C++实现)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 二叉树题目:二叉树的层序遍历 II

    标题:二叉树的层序遍历 II 出处:107. 二叉树的层序遍历 II 4 级 要求 给你二叉树的根结点 root texttt{root} root ,返回其结点值自底向上的层序遍历(即从左到右,按从叶结点所在层到根结点所在层逐层遍历)。 示例 示例 1: 输入: root   =   [3,9,20,null,null,15,7] texttt{root = [3

    2024年02月11日
    浏览(35)
  • day15 层序遍历 翻转二叉树 对称二叉树

    题目链接:102 二叉树的层序遍历 题意 根据二叉树的根节点root,返回其节点值的层序遍历 借助队列实现,因为队列是先进先出的逻辑,符合层序遍历一层一层遍历的思想 代码 题目链接:226 翻转二叉树 题意 根据二叉树的根节点root,翻转二叉树,将节点是左右孩子进行翻转

    2024年01月22日
    浏览(47)
  • ★102. 二叉树的层序遍历

    很巧妙的,又学习了一种层次遍历的方法, 就是说根据当前的队列的长度去遍历,遍历的当前队列的长度就是该层次的节点个数。

    2024年02月05日
    浏览(43)
  • 41 二叉树的层序遍历

    给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。 提示: 树中节点数目在范围 [0, 2000] 内 -1000 = Node.val = 1000

    2024年02月07日
    浏览(46)
  • Java层序遍历二叉树

    二叉树准备: 力扣

    2024年01月23日
    浏览(30)
  • LeetCode 0103.二叉树的锯齿形层序遍历:层序遍历 + 适时翻转

    力扣题目链接:https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/ 给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。   示例 1: 示例 2: 示例 3:   提示: 树中节点数目在范

    2024年02月20日
    浏览(39)
  • 二叉树的遍历(节点个数及层序遍历)

     简易树的图形:    运行实例: 以A节点开始运算的节点个数 以B节点开始运算的节点个数 解释(图解+文字解释):  把A传过去A不为空,进入left,A的left为B不为空,B的left为D不为空,D的left和right都为空返回0+0+1,在进入B的right,B的right为E不为空,E的left和right都为空返回

    2023年04月22日
    浏览(52)
  • 数据结构——二叉树层序遍历

    来喽来喽~ 二叉树的层序遍历来喽~ 层序遍历那是相当有趣滴! 我的朋友,请不要迷惘,你要记住,你终有鲲鹏一日! 加油吧!从现在开始~ 层序遍历 :除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1,层序遍历就是从所

    2024年02月07日
    浏览(46)
  • day15 | 层序遍历、 226.翻转二叉树、 101. 对称二叉树

    目录: 题目链接: 层序遍历 给你二叉树的根节点  root  ,返回其节点值的  层序遍历  。 (即逐层地,从左到右访问所有节点)。 随想录:借助一个队列实现。 102. 二叉树的层序遍历 107.二叉树的层次遍历 II 最后只需要将result的顺序改一下就行,但是注意,reverse是直接

    2024年02月08日
    浏览(74)
  • 【C++】102.二叉树的层序遍历

    给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。 示例1: 示例 2: 示例 3: 提示: 树中节点数目在范围 [0, 2000] 内 -1000 = Node.val = 1000 这个问题实际上可以只用一个队列就实现,只需要再增加一个变量 levelSize ,用来记录每一层

    2024年03月11日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包