首页 > 其他分享 >先(后)序遍历确定唯一二叉树

先(后)序遍历确定唯一二叉树

时间:2024-08-03 13:38:55浏览次数:9  
标签:遍历 cn 唯一 确定 二叉树 序列 节点

在二叉树的先序遍历或后序遍历序列中,如果我们记录了空节点的位置(通常用特殊符号如'#'表示),就足以唯一确定一棵二叉树的结构。

这种方法的关键在于,记录空节点的位置能够帮助我们在遍历序列中准确地还原出树中节点的结构信息。因此,只要给出了先序遍历或后序遍历序列以及空节点的位置,就能够确定一棵二叉树,而不需要额外通过中序遍历序列来确定二叉树。
两道力扣题

LeetCode 331: https://leetcode.cn/problems/verify-preorder-serialization-of-a-binary-tree/description/
LeetCode 652: https://leetcode.cn/problems/find-duplicate-subtrees/

标签:遍历,cn,唯一,确定,二叉树,序列,节点
From: https://www.cnblogs.com/Biang-blog/p/18340375

相关文章

  • 数据结构--------二叉树的定义及遍历操作的实现
    /*二叉树的链式存储以及基本操作*/#include<stdio.h>#include<stdlib.h>//树的节点typedefstructBTNode{intdata;structBTNode*lchild;structBTNode*rchild;}BTNode,*BTTree;/......
  • 【MFC】树控件递归遍历
    //本树只有一个父节点,最深子节点为2级,拥有复选框//遍历树控件(只有一个父节点,命名为“所有模板”)voidCCheckOverLapDlg::TraverseTree(CTreeCtrl*pTreeCtrl){ CStringstrParent=_T("所有模板"); //主函数入口 TraverseTreeBranch(pTreeCtrl,pTreeCtrl->GetRootItem(),......
  • 【代码随想录训练营第42期 Day17打卡 二叉树Part5-LeetCode 654.最大二叉树 617.合并
    目录一、做题心得二、题目与题解题目一:654.最大二叉树题目链接题解:递归题目二:617.合并二叉树题目链接题解:递归(前序遍历)题目三:617.合并二叉树题目链接题解:BFS层序遍历 题目四:98.验证二叉搜索树题目链接题解:递归(中序遍历)三、小结一、做题心得今天是代码随想......
  • java集合的三种遍历方式
    一、迭代器遍历 在遍历过程中,想删除元素可以使用迭代器遍历ps:遍历过程中不能用集合的方法进行遍历,可以用指针的remove方法进行遍历二、增强for遍历idea快捷方式集合名字.for加回车。方法的底层也是利用迭代器三、lambda表达式遍历完整格式简单格式......
  • 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:=......
  • 数据结构:二叉树(链式结构)
    文章目录1.二叉树的链式结构2.二叉树的创建和实现相关功能2.1创建二叉树2.2二叉树的前,中,后序遍历2.2.1前序遍历2.2.2中序遍历2.2.3后序遍历2.3二叉树节点个数2.4二叉树叶子结点个数2.5二叉树第k层结点个数2.6二叉树的深度/高度2.7二叉树查找值为x的结点2.8......
  • 图解平衡二叉树
    平衡二叉树平衡二叉树的背景由于一些众所周知的原因,我们选择了平衡二叉树,好吧,其实就是因为对二叉搜索树的限制太少了,导致在一些特殊的情况下,二叉搜索树不太听话,查找,插入与删除的时间均变成了\(O(n)\)也可以认为,熵增就会更加有序,熵减就会更加自由,这里我们......
  • DAY 15 二叉树part03
      110.平衡二叉树(优先掌握递归)题目链接/文章讲解/视频讲解:https://programmercarl.com/0110.%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91.html 独立完成,感觉还比较好理解12classSolution{13public:14boolisBalanced(TreeNode*root){15if(......
  • 数据结构----树,二叉树,哈夫曼树相关概念及其实现
    树形结构概述1分层逻辑结构所谓的分层逻辑结构,也称为树形逻辑结构关系,是数据结构中的一种逻辑关系结构,在该逻辑结构关系中的数据元素之间满足一对多的逻辑结构关系:起始数据节点有且仅有一个,没有直接前驱,可以有多个直接后继;末尾数据节点可以多个,有且仅有一个直接前驱,......