当前位置 : 主页 > 编程语言 > c语言 >

数据结构-->二叉树_OJ_03

来源:互联网 收集:自由互联 发布时间:2023-09-07
老友们好,欢迎来到本期博文!!今天,为大家带来两道 OJ 题讲解! 不过,今天的二叉树 OJ 题就要结束了!接下来,会转入 二叉树的堆栈 !! 1.布尔判断你另一棵树 为了加深,对题

老友们好,欢迎来到本期博文!!今天,为大家带来两道 OJ 题讲解!

不过,今天的二叉树 OJ 题就要结束了!接下来,会转入 二叉树的堆栈 !!

1.布尔判断你另一棵树

数据结构-->二叉树_OJ_03_二叉树遍历操作的创新思维

为了加深,对题意的理解,现附上题意解析图示 :>

数据结构-->二叉树_OJ_03_二叉树遍历操作的创新思维_02

各位老友,请一定要加深,对题意的第二句话理解!!重要,重要,很重要!!如果,对这句话,理解不深的话,接下来的代码操作,会糊涂的!!

接下来,我们就上手代码了!

//布尔判断相同的树
typedef int BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
}BTNode;

bool isSubtree(BTNode* root, BTNode* subRoot)
{
	if(root == NULL && sunRoot == NULL)
  {
    return true;
  }
  
  if(root == NULL || subRoot == NULL)
  {
  	return false;
  }
  
  if(root -> data != subRoot ->data)
  {
  	return false;
  }
  
  return isSameTree(root ->left, subRoot ->left)
    	&& isSameRoot(root ->right, subRoot ->right);
}

bool isSubtree(BTNode* root, BTNode* subRoot)
{
	if(root == NULL)
  {
  	return false;
  }
  
  if(isSameTree(root, subroot))
  {
  	return true;
  }
  
  return isSubtree(root ->left, subRoot)
    	|| isSubtree(root ->right, subRoot);
}

为了有更好的观感体验,现特此附上有彩色的代码图样 :>

数据结构-->二叉树_OJ_03_二叉树遍历操作的创新思维_03


其实,该部分的代码,与前几期思想逻辑上,基本上是完全相同的!!上部分的代码,就不多做解析了!!

如有疑问,请老友们自行观看前几期的博文,那里有你要找的答案!!

现在对以上部分代码较难理解的部分,进行解析 :>

数据结构-->二叉树_OJ_03_二叉树遍历操作的创新思维_04


请看上图,已经划分了三个小部分,这些都是学习的时候,容易掉进坑的地方!!

第一部分 :

条件判断句里,有一个布尔判空,那么逻辑上应该怎么走呢?

-----> 当上部分  “isSameTree()” 函数为真的时候,会进入,否则会直接跳过!!也是说,递归遍历,直至全为空的时候,就是符合条件的时候!!

这里的全为空,有两种解释:

一上来,就是空,还没有递归遍历就符合条件了;

二是,进行了递归操作,两颗子树最终,都走向了叶子结点。

否则,上述任何一步,只要不合符合条件,就会直接跳过!!

第二部分 :

为何,递归遍历当中,第二个参数,直接就是子树呢?为什么没有指明左右情况呢?

还记得,题意的要求与提示吗!这里,需要加深对第二句题意的理解!!

-----> 要看成一个整体,而 Root 树,根结点不为空的时候,继续的走向,是递归遍历,先左子树,然后是右子树

而 SubRoot 树 虽然是一颗二叉树,但是其本体可看成是自身的子树!!

希望,有关于对第二部分的解析,可以解答老友们的困惑 !!

第三部分

操作符号 “| |” 的运用,而不是 “&&”

此时,部分老友,可能认为,这是一句滥充字数的书写 !!因为逻辑上很简单!!几乎可以忽略解释 !!

有鉴于, 本人追求一种完整性,还是讲解一下的好 !!

“| |” 操作符的使用,是有一个为假,也不会停止上述的递归遍历,只有当两者甚至三者以上全部为假的时候,才会停止执行逻辑上的操作!!

这里,二叉树有左右子树;递归遍历完成左子树之后,可别忘记了,还有右子树需要递归遍历 !!

至此,本道 OJ 题已经讲解完成了 !!希望老友们,能有所收获

上一篇:C语言——数组
下一篇:没有了
网友评论