数据结构-->二叉树 OJ_01

经过前几期浴血奋战！！二叉树便要进入应用阶段了！今天，为大家带来几道 OJ 题的讲解！

1.单值二叉树

如果二叉树每个结点都具有相同的值，那么该二叉树就是单值二叉树

只有给定的树是单值二叉树时， 才会返回 true, 否则返回 false

下面为了方便理解，进行图解举例 ：>

有上述的两种情况，其中还需要考虑到空节点的情况

现在上手代码，如下 ：>

typedef int BTDataType;

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


//布尔判断单值二叉树
bool isUniverTree(BTNode* root)
{
	if(root == NULL)
    return true;
  
  if(root ->left && root ->left ->data != root ->data)
  {
  	return false;
  }
  
  if(root ->right && root ->right ->data != root ->data)
  {
  	return false;
  }
  
  return isUniverTree(root ->left) && isUniverTree(root ->right);
}

为了方便大家，能有更好的观感体验，特附上有色彩图样代码 ：>

另外，多讲一句废话！！上述代码，依靠强大的递归实现！！对递归是有要求的！！

2.相同的树

给定两颗二叉树的根结点 p 和 q， 编写一个函数来检验这两棵树是否相同！

如果两棵树在结构上相同，并且结点具有相同的值，则认为这两棵树相同！

本道 OJ 题，思路该如何打开呢？

-----> 既然是根结点，那么不可避免的是空结点的考虑！

下一步，则是存在根结点至少有一个不为空，那么言外之意是，有可能该两个根结点都不为空

此种情况的对应，是下列代码的，第二个 条件判断句，以及第三个 条件判断句

现在手搓代码 ：>

typedef int BTDataType;

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

//布尔判断相同二叉树
bool isSameTree(BTNode* p, BTNode* q)
{
	if(p == NULL && q == NULL)
  {
		return true;  	
  }
  
  //至少有一个不为空
  if(p == NULL || q == NULL)
  {
  	return false;
  }
  
  //两个根结点都不为空
  if(p ->data != q ->data)
  {
  	return false;
  }
  
  //左子树递归遍历 && 右子树递归遍历
  return isSameTree(p ->left, q ->left)
    		&& isSameTree(p ->right, q ->right);
}

为了方便大家观感，特别附上彩色代码图样 :>

另外，注意一点，可能会有部分老友，对上述的解析看不懂

比如说，根结点的情况，当递归遍历的时候，从那个起始点开始，就当做了根结点！！

不知这样解说，是否已经足够清晰了！！